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.