Some of the problems seem to be due to the complexity of the document. My 480 page, 20000 paragraph test document had over 4000 bookmarks most of which were dormant, and 700 REF fields. Converting the fields to text and removing unused bookmarks gave a big improvement to the timing. With the TOC visible the timing came down from 30 minutes to 2 minutes. If the TOC is not visible then the timing came down from 80 to 28 seconds.
Therefore:
The timing is dependent of a whole heap of factors, not just the number of paragraphs. The visibility of the TOC is just one of them.
For large documents, if the screen is displaying a TOC it is well worth jumping to another page before executing the For Each… code.