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.
I am having trouble getting keyboard Maestro to take the Cmd-A and the Option, Cmd-F to Select all and then go into find and replace.
If you are having trouble, you should probably describe exactly what your trouble is, or perhaps even upload your macro.
Pages Sermon Outline Title copy
Prompt for User Input “Enter the values for the Pages document”
Type the ⌘A Keystroke
Type the ⌥⌘F Keystroke
Insert Text “?Title” by Typing
Type the Tab Keystroke
Type the Tab Keystroke
Type the Tab Keystroke
Insert Text “%Variable%Local_Title%” by Typing
Type the Tab Keystroke
Type the Tab Keystroke
Type the Tab Keystroke
Type the Tab Keystroke
Type the Tab Keystroke
Type the Enter Keystroke