In Word VBA, calling doc.Paragraphs(idx) to get a paragraph by its index is very slow. Instead, once you have a Paragraph object, use para.Next and para.Previous to navigate, and your code will be much faster! I just refactored an old routine this way and received a dramatic speedup.
I think doc.Paragraphs() must be iterating through the document starting from the beginning, but I don’t know that for sure. I do know that adding paragraphs before the region my code was working with made the code run perceptibly slower, even though the code was never touching the added paragraphs.
Here are some simple helpers, in case you want to manually check for errors rather than throwing when you run off the end of the document:
Private Function NextParaOrNothing_(p As Paragraph) As Paragraph
Set NextParaOrNothing_ = Nothing
On Error Resume Next
Set NextParaOrNothing_ = p.Next
End Function 'NextParaOrNothing_
Private Function PrevParaOrNothing_(p As Paragraph) As Paragraph
Set PrevParaOrNothing_ = Nothing
On Error Resume Next
Set PrevParaOrNothing_ = p.Previous
End Function 'PrevParaOrNothing_