I also ran the test on a much larger document - 1458 pages (~500,000 paragraphs) of your sample text, then did a Find/Replace with:
Find = ^p^p
Replace = ^p
153,600 replacements were made.

In Print Layout view (and Draft view), there are most definitely things you can't do while Word is repaginating the document after such a Find/Replace. Hence, it will be slower when repagination is allowed. It will also be slower if Word is continually trying to spell-check the document. Turning off auto-save would likely also increase responsiveness in such a large document.

Word is a word-processor, with all that entails. Clearly, you're not using Word for the purpose for which it was designed.

Word also handles ordinary 4Mb word-processing documents in its stride. I have some as large as 15Mb and more, all of which Word handles with ease.

Since you already have a solution (Notepad++) for your peculiar requirements, use that.

__________________
Cheers,
Paul Edstein
[Fmr MS MVP - Word]