Finding text in a PDF can be inherently hard because of the graphical nature of the document format — the letters you are searching for may not be contiguous in the file. That said, CAM::PDF has some search-replace capabilities and heuristics. Give changepagestring.pl a try and see if it works on your PDFs.
To install:
$ cpan install CAM::PDF
# start a new terminal if this is your first cpan module
$ changepagestring.pl input.pdf oldtext newtext output.pdf