You don't need to "Select All" -- if nothing is selected the whole document will be find-and-replaced, including headers and footers.
You may need to include a check that the dialog is in "Find and Replace" mode rather than plain "Find", as it appears to remember what was done last.
But yes, this will be much easier (and, IIRC from other attempts, more reliable) than AppleScripting the replacement.