Você pode tentar pdftk , mas funciona apenas uma fração do tempo, devido a (eu acredito) um problema com fontes.
Funciona assim: primeiro você precisa descompactar o arquivo pdf,
pdftk myfile.pdf output unc.pdf uncompress
depois modifique-o com
sed 's/oldstring/newstring/g' < unc.pdf > mod_unc.pdf
por último você recompacta com
pdftk mod_unc.pdf output myfile_modified.pdf compress
Eu tive apenas um sucesso moderado com este comando, no sentido de que às vezes funciona, às vezes não, de acordo com o capricho.