You could very well end up with a disaster if you're not careful. I would start with the paragraphs first as spans can get a bit hairy.
If you're absolutely sure that you want to change
everything that has a class name of "MsoNormalXX" (X being numerals) to "paragraphtext", then:
Find: <p class="MsoNormal\d+">
Replace: <p class="paragraphtext">
Make sure you have good backups in case things don't turn out the way you've planned.