A few ideas for you to try:

1. Open the document. Type CTRL-F. Click on the replace tab and find&replace away.
2. Use Win32::OLE. This will be more difficult but will allow automation
3. Use Text::Extract::Word to extract the text and then use Win32::Word::Writer to recreate the document.

Hope this helps some. This will be pretty difficult since you are new to Perl but that's just the way it is with the task you have. Feel free to ask for help with other issues that arise.