Tagging links in headers / footers

It appears that you are taking an HTML markup approach to PDF.
That's a big *no start*.

The seminal references for accessible PDF are ISO 14289, PDF/UA - The ISO Standard that defines/describes what, specifically, an "accessible" PDF is / must be (available from AIIM for $15) and ISO 32000, PDF-Ref the ISO Standard that defines/describes what, specifically, PDF is.

Note that the Section 508 refresh that'll one day be a done deal has ISO 14289 incorporated by reference as the standard for PDF. When there is content in a PDF that is not specifically "of PDF" (say an audio clip) you're pointed to WCAG 2.0 / whatever other standard is applicable).

In an Accessible PDF:

Regarding headers / footers - these are Artifacts. This is a "Shall requirement.
See clause 7.8 of ISO 14289-1. Artifacts are ignored by AT.

Regarding post-processing PDF to place Link elements (tags) - First, The "wizard" in Acrobat will not (as you've observed) be able to do this. You must do it manually and with the proper method.

"Link" is an Inline-Level Structure Element. Consequently it "lives" within (in-line) a Block-Level Structure Element.  So, a run of text (say one or more sentences) is associated with the Paragraph "P" element.

Some authoring application "style" name may be show (e.g., from Word this might be "Normal"). Regardless it is a requirement for accessible PDF that such role map to the appropriate PDF element/tag (i.e., "P" in this case).

"P" could identify:

        Some text & more text & not less text. Some text and then some "a link string here" with some more text.

The "Link" element is going to be within the "P". Specifically it will be the "box" placed over the "a link string here".

You could select the string "a link string here" then right click for the context menu. On the context menu click the choice "Create Link".
View the structure tree to confirm the placement of the required components that comprise an accessible Link.

Remember to provide the Link its required alternate text description (required by ISO 14289-1, 7.8.5).

An alternative work flow:

From Adobe Accesible PDF documentation:

Adding Accessible Links (to a PDF) –

Acrobat provides several ways to create active links for text, objects, and URLs in a PDF document.
However, because the methods differ in how they affect the tag tree, Adobe recommends only one method at this stage in the workflow: activating each link manually by using the Create Link command (on the context menu - with the string that is to have the Link annotation placed over it selected you right click for the context menu and "create link" is available).

Unlike the other methods for creating links in a tagged PDF document (by using the Links tool or the Create From URLs In Document command),
using the Create Link command adds all three tags that screen readers require in order to recognize a link.
The other methods create only one of the three tags, which means that you must manually edit the tag tree
to add the remaining two tags for each link and place these tags in the proper reading order in the tree.
Although you must activate links one by one, using the Create Link command provides the fastest results
and the least amount of follow-up work to make the links accessible to screen readers.
All that you need to do afterward is edit the tag tree to add alternate text to the new links.

You must use Acrobat Professional to perform this accessibility task, and to add alternate text to links.
Creating links by using Acrobat Standard does not generate any tags for the links.

This Captivate video may be helpful:

http://daka630.com/learning/acrobat/s508/AccessLink/s508CpAccessibleLink.html  Using Create Link for Accessible Links in a PDF

Be well...