Perhaps there is something wrong with your system.

I just created a document containing 375 pages (7306 paragraphs) of your sample text, then did a Find/Replace with:
Find = ^p^p
Replace = ^p
The process took about 1 second to complete. Even creating said document was a breeze.

As designed, Word can handle documents up to 512Mb in size, including 32Mb of text.

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

I doubt if it is the system. The exact same behavior manifests in all computers that I have tried these docs, and they are all modern machines with adequate RAM, new OS and new Office. Also, there seems to be some threshhold for this behavior. The size you cite in your test is well within the bounds of what still works quite well. If you want a test of the sizes I am dealing with, duplicate the text to get 15,000 pages, instead of 375.