When I'm faced with a task like this, I create a batch file to do the work. Word's ability to work with columns (create a table, paste, edit, then export the text or simply remove the table attribute) makes the task a set of global find and replace.
Other better word processors should be able to do the same kind of tricks.
Depends on my level of laziness. You can dump the filenames to a text file with a dir /b >ren.bat then use a real text editor like notepad++ and add the rename to the start of every line and the new name to the end of every line. your filename is already a batch file from step 1
or you can master the intricacies of the for command mixed in with some grep goodness and spend an hour debugging a batch file, and completely forget how the for command works by the next day.