PowerShell workaround for the blank Header/Footer

I am trying to put together a PowerShell script to do multiple find and replace throughout a whole Word Document, that is including Headers, Footers and any Shape potentially displaying text.
There are plenty of VBA examples around so it's not too difficult, but there is a know bug that is circumvented in VBA with a solution dubbed as "Peter Hewett 's VBA trickery". See this example and also this one.
I have tried to address this bug in a similar fashion in PowerShell but it is not working as expected. Some TextBoxes in Header or Footer are still being ignored.
I noticed however, that runnning my script twice will actually end up working.

Any idea as to a solution to this problem would be greatly appreciated.

$folderPath = "C:\Users\user\folder\*" # multi-folders: "C:\fso1*", "C:\fso2*"
$fileType = "*.doc"                    # *.doc will take all .doc* files

$textToReplace = @{
# "TextToFind" = "TextToReplaceWith"
"This1" = "That1"
"This2" = "That2"
"This3" = "That3"
}

$word = New-Object -ComObject Word.Application
$word.Visible = $false

$storyTypes = [Microsoft.Office.Interop.Word.WdStoryType]
#Val, Name
#  1, wdMainTextStory
#  2, wdFootnotesStory
#  3, wdEndnotesStory
#  4, wdCommentsStory
#  5, wdTextFrameStory
#  6, wdEvenPagesHeaderStory
#  7, wdPrimaryHeaderStory
#  8, wdEvenPagesFooterStory
#  9, wdPrimaryFooterStory
# 10, wdFirstPageHeaderStory
# 11, wdFirstPageFooterStory
# 12, wdFootnoteSeparatorStory
# 13, wdFootnoteContinuationSeparatorStory
# 14, wdFootnoteContinuationNoticeStory
# 15, wdEndnoteSeparatorStory
# 16, wdEndnoteContinuationSeparatorStory
# 17, wdEndnoteContinuationNoticeStory

Function findAndReplace($objFind, $FindText, $ReplaceWith) {
  #simple Find and Replace to execute on a Find object
  $matchCase = $true
  $matchWholeWord = $true
  $matchWildcards = $false
  $matchSoundsLike = $false
  $matchAllWordForms = $false
  $forward = $true
  $findWrap = [Microsoft.Office.Interop.Word.WdReplace]::wdReplaceAll
  $format = $false
  $replace = [Microsoft.Office.Interop.Word.WdFindWrap]::wdFindContinue

  $objFind.Execute($FindText, $matchCase, $matchWholeWord, $matchWildCards, $matchSoundsLike, $matchAllWordForms, \`
           $forward, $findWrap, $format, $ReplaceWith, $replace) > $null
}

Function findAndReplaceAll($objFind, $FindText, $ReplaceWith) {
    findAndReplace $objFind $FindText $ReplaceWith
    While ($objFind.Found) {
        findAndReplace $objFind $FindText $ReplaceWith
    }
}

Function findAndReplaceMultiple($objFind, $lookupTable) {
  #apply multiple Find and Replace on the same Find object
  $lookupTable.GetEnumerator() | ForEach-Object {
    findAndReplaceAll $objFind $_.Key $_.Value
  }
}

Function findAndReplaceMultipleWholeDoc($Document, $lookupTable) {
  ForEach ($storyRge in $Document.StoryRanges) {
    #Loop through each StoryRange
    Do {
      findAndReplaceMultiple $storyRge.Find $lookupTable
      #check if the StoryRange has shapes (we check only StoryTypes 6 to 11, basically Headers and Footers)
      # as the Shapes inside the wdMainTextStory will be checked
      # see http://wordmvp.com/FAQs/Customization/ReplaceAnywhere.htm
      # and http://gregmaxey.com/using_a_macro_to_replace_text_wherever_it_appears_in_a_document.html
      If (($storyRge.StoryType -ge $storyTypes::wdEvenPagesHeaderStory) -and \`
        ($storyRge.StoryType -le $storyTypes::wdFirstPageFooterStory)) {
        If ($storyRge.ShapeRange.Count) { #non-zero is True
          ForEach ($shp in $storyRge.ShapeRange) {
            If ($shp.TextFrame.HasText) { #non-zero is True, in case of text .HasText = -1
              findAndReplaceMultiple $shp.TextFrame.TextRange.Find $lookupTable
            }
          }
        }
      }
      #check for linked Ranges
      $storyRge = $storyRge.NextStoryRange
    } Until (!$storyRge) #non-null is True

  }
}

Function processDoc {
  $doc = $word.Documents.Open($_.FullName)
  # The "VBA trickey" translated to PowerShell...
  $junk = $doc.Sections.Item(1).Headers.Item(1).Range.StoryType
  #... but not working
  findAndReplaceMultipleWholeDoc $doc $textToReplace
  $doc.Close([ref]$true)
}

$sw = [Diagnostics.Stopwatch]::StartNew()
$countf = 0
Get-ChildItem -Path $folderPath -Recurse -Filter $fileType | ForEach-Object { 
  Write-Host "Processing \`"$($_.Name)\`"..."
  processDoc
  $countf++
}
$sw.Stop()
$elapsed = $sw.Elapsed.toString()
Write-Host "Done. $countf files processed in $elapsed"

$word.Quit()
$word = $null
[gc]::collect() 
[gc]::WaitForPendingFinalizers()

I checked out Microsoft documentation documentation here and then I think the below code can do it.

$word = New-Object -ComObject Word.Application
$word.visible=$false
$files = Get-ChildItem "C:\Users\Ali\Desktop\Test" -Filter *.docx

$find="Hello"
$replace="Bye"
$wdHeaderFooterPrimary = 1


$ReplaceAll = 2
$FindContinue = 1
$MatchCase = $false
$MatchWholeWord = $false
$MatchWildcards = $false
$MatchSoundsLike = $false
$MatchAllWordForms = $false
$Forward = $true
$Wrap = $findContinue
$Format = $false


for ($i=0; $i -lt $files.Count; $i++) {
$filename = $files[$i].FullName 
$doc = $word.Documents.Open($filename)


ForEach ($StoryRange In $doc.StoryRanges){

$StoryRange.Find.Execute($find,$MatchCase,
                        $MatchWholeWord,$MatchWildcards,$MatchSoundsLike,
                        $MatchAllWordForms,$Forward,$Wrap,$Format,
                        $replace,$ReplaceAll)

 While ($StoryRange.find.Found){
        $StoryRange.Find.Execute($find,$MatchCase,
                        $MatchWholeWord,$MatchWildcards,$MatchSoundsLike,
                        $MatchAllWordForms,$Forward,$Wrap,$Format,
                        $replace,$ReplaceAll)
 }



  While (-Not($StoryRange.NextStoryRange -eq $null)){
   $StoryRange = $StoryRange.NextStoryRange


           $StoryRange.Find.Execute($find,$MatchCase,
                        $MatchWholeWord,$MatchWildcards,$MatchSoundsLike,
                        $MatchAllWordForms,$Forward,$Wrap,$Format,
                        $replace,$ReplaceAll)


    While ($StoryRange.find.Found){
          $StoryRange.Find.Execute($find,$MatchCase,
                        $MatchWholeWord,$MatchWildcards,$MatchSoundsLike,
                        $MatchAllWordForms,$Forward,$Wrap,$Format,
                        $replace,$ReplaceAll)
    }
    } 

}

  #shapes in footers and headers
for ($j=1; $j -le $doc.Sections.Count; $j++) {

    $FooterShapesCount = $doc.Sections($j).Footers($wdHeaderFooterPrimary).Shapes.Count
    $HeaderShapesCount = $doc.Sections($j).Headers($wdHeaderFooterPrimary).Shapes.Count

        for ($i=1; $i -le $FooterShapesCount; $i++) {
            $TextRange = $doc.Sections($j).Footers($wdHeaderFooterPrimary).Shapes($i).TextFrame.TextRange
            $TextRange.Find.Execute($find,$MatchCase,
                        $MatchWholeWord,$MatchWildcards,$MatchSoundsLike,
                        $MatchAllWordForms,$Forward,$Wrap,$Format,
                        $replace,$ReplaceAll)
        }
        for ($i=1; $i -le $HeaderShapesCount; $i++) {
            $TextRange = $doc.Sections($j).Headers($wdHeaderFooterPrimary).Shapes($i).TextFrame.TextRange
            $TextRange.Find.Execute($find,$MatchCase,
                        $MatchWholeWord,$MatchWildcards,$MatchSoundsLike,
                        $MatchAllWordForms,$Forward,$Wrap,$Format,
                        $replace,$ReplaceAll)
        }
    }
$doc.Save()
$doc.close()
}

$word.quit()