Same happened to me.
I tried to edit normal.dot/normal.dotm and add header, but I couldn't find it anywhere, even in hidden folders.
I also deleted complete MicrosoftOffice 2013 and reinstalled it, but nothing improved.