Restrict Editing Header Footer in Word Document

1. Click On Restrict Editing

2. In the Restrict Editing pane, 

•  Do not check the box under "1. Formatting restrictions",
•  Do check the box under "2. Editing restrictions" and leave the drop down set to "No  changes (Read only)".

3. Select the entire body of the document (Ctrl+A).

4. In the Restrict Editing pane, check the box next to Everyone under the Exceptions section. 

5. Then start enforcing protection and save the template.

6. Basically, the "No changes" protection is applied only to the header and footer, the only parts that weren't selected when you checked "Everyone".