PowerShell script to Find and Replace in Word Document, including Header, Footer and TextBoxes within
COM Automation (which is what you are using) is always going to be slow. There's not much you can do about that except to try find new ways to do what you want with as few operations as possible. 

An alternative you could investigate is the Open XML SDK. I've never tried it myself, but it is supposed to be a lot faster than COM Automation.

The Open XML SDK is a .NET library, so there should be no problem calling it from PowerShell, but you will have to translate the example code from C# or VB.NET into PowerShell.

Here's an example for Excel which you could adapt. Or maybe you could find an actual Word example. I didn't search very hard.

You should also check out Open-XML-PowerTools. This is a PowerShell wrapper for the Open XML SDK. Maybe it will do what you want already. 

Here's a screencast that shows searching and replacing using  Open-XML-PowerTools.