You could try to restrict to the pages that you're interested in
before enumerating them:
var flag = Microsoft.Office.Interop.Word.WdInformation.wdActiveEndPageNumber;
var desiredParagraphs = document.Paragraphs.Where(p => {
int endPage = p.Range.Information[flag];
return (endPage < 2552) || ((endPage > 2620) && (endPage < 2695)) || (endPage > 2954);
});
foreach (Microsoft.Office.Interop.Word.Paragraph MyParagraph in desiredParagraphs)
{
}
Hopefully that will save some enumerations, maybe enough to get rid of the performance issue.