This is not a project to be lightly undertaken if it is possible at all. How
many thousands of documents on how many machines? Version of Word? What,
exactly, are you trying to do? Why?

If you have a programmable hex editor, you had best consult that newsgroup
as well.

I would do it from within Word using vba, if at all.

The easiest way to do something like this is before the documents are
created, set up a template that has your page numbering. For simple Word
documents, you could copy contents from the old document to a new one based
on your template, losing what is already in the header/footer.