Allgemein kann man den Kolumnentitel jederzeit mit Hilfe von `\markright` oder `\markboth` ändern:
\documentclass{article}
\usepackage[ngerman]{babel}
\usepackage{mwe}
\pagestyle{headings}
\begin{document}
\tableofcontents
\blinddocument
\appendix
\section*{Anhang}
\addcontentsline{toc}{section}{Anhang}
\markright{Anhang}
\Blindtext[5]
\end{document}
Dabei ist aber zu beachten, dass teilweise in den eigentlich für die Kolumnentitel verwendeten Anweisungen, beispielsweise `\sectionmark`, ggf. auch weitere Formatierungsbefehle enthalten sind, die dann ggf. übernommen werden müssten, damit der Kolumnentitel zu den restlichen Kolumnentiteln passt. Im obigen Beispiel wäre das `\MakeUppercase`:
\documentclass{article}
\usepackage[ngerman]{babel}
\usepackage{mwe}
\pagestyle{headings}
\begin{document}
\tableofcontents
\blinddocument
\appendix
\section*{Anhang}
\addcontentsline{toc}{section}{Anhang}
\markright{\MakeUppercase{Anhang}}
\Blindtext[5]
\end{document}
Wird später dann die Formatierung der normalen Kolumnentiteln geändert, so muss man auch alle `\markboth` und `\markright`-Anweisungen ändern. Daher ist es besser, sich in der Präambel eine eigene Anweisung zu definieren, so dass man ggf. nur diese eine zentral ändern muss:
\documentclass{article}
\usepackage[ngerman]{babel}
\usepackage{mwe}
\pagestyle{headings}
\newcommand*{\sectionmarknonumber}[1]{\markright{\MakeUppercase{#1}}}
\begin{document}
\tableofcontents
\blinddocument
\appendix
\section*{Anhang}
\addcontentsline{toc}{section}{Anhang}
\sectionmarknonumber{Anhang}
\Blindtext[5]
\end{document}
Natürlich könnte man dann auch gleich eine komplette Anweisung `\sectionnonumber` definieren, die sowohl die Überschrift setzten, als auch den Inhaltsverzeichniseintrag erzeugt, als auch den Kolumnentitel vornimmt. Will man dabei wie bei `\section` auch ein optionales Argument ermöglichen, landet man im Endeffekt bei dem, was [die KOMA-Script-Klassen](http://www.ctan.org/pkg/koma-script) bereits mit `\addsec` (und auf Teile- und Kapitelebene auch mit `\addpart` und `\addchap`) bieten:
\documentclass{scrartcl}
\usepackage[ngerman]{babel}
\usepackage{mwe}
\pagestyle{headings}
\begin{document}
\tableofcontents
\blinddocument
\appendix
\addsec{Anhang}
\Blindtext[5]
\end{document}
Teilweise bieten auch andere Klassen, beispielsweise [`memoir`](http://www.ctan.org/pkg/memoir) Möglichkeiten nicht nummerierte Überschriften mit Inhaltsverzeichniseintrag und Kolumnentitel zu erzeugen. Näheres ist der Anleitung der jeweiligen Klasse zu entnehmen.
---------
Allgemein sei noch darauf hingewiesen, dass Überschriften besser einen Bezug zum Inhalt als zur Dokumentstruktur haben sollten. Man [Man sollte also nicht »Anhang« in die Überschrift schreiben, schreiben](http://texwelt.de/wissen/fragen/19227/wie-setzt-man-korrekt-einen-anhang), sondern beispielsweise »Abbildungen« (wenn es sich um einen Anhang mit Abbildungen handelt) oder »Ergänzungen«. Damit spricht dann auch nichts mehr dagegen, diesen Anhang zu nummerieren:
\documentclass{article}
\usepackage[ngerman]{babel}
\usepackage[utf8]{inputenc}
\usepackage{mwe}
\pagestyle{headings}
\begin{document}
\tableofcontents
\blinddocument
\appendix
\section{Ergänzungen}
\Blindtext[5]
\end{document}
Wie man sieht, kann man dabei die Anhänge sehr gut an der durch `\appendix` automatisch geänderten Nummerierungsart erkennen. Braucht man doch irgendwie ein »Anhang«, so wäre die Teile-Ebene dafür eher geeignet. Die Struktur des Anhangs selbst bleibt dann nämlich konsistent mit der Struktur des Hauptteils:
\documentclass{article}
\usepackage[ngerman]{babel}
\usepackage{mwe}
\pagestyle{headings}
\begin{document}
\tableofcontents
\blinddocument
\appendix
\section{Anhang}
\Blindtext[5]
\end{document}
Bei Verwendung einer KOMA-Script-Klasse kann man auch bei dieser Ebene automatisch einen Eintrag ins Inhaltsverzeichnis vornehmen lassen:
\documentclass{scrartcl}
\usepackage[ngerman]{babel}
\usepackage[utf8]{inputenc}
\usepackage{mwe}
\pagestyle{headings}
\begin{document}
\tableofcontents
\blinddocument
\appendix
\addpart{Anhang}
\section{Ergänzungen}
\Blindtext[5]
\end{document}
Weiterführende Betrachtungen dazu sind bei der Frage »[Wie setzt man korrekt einen Anhang?](http://texwelt.de/wissen/fragen/19227/wie-setzt-man-korrekt-einen-anhang)« zu finden.