Scribus peut-être une solution. C'est un logiciel libre disponible pour Linux/Windows/Mac OS. Il peut être téléchargé gratuitement depuis de nombreux site.
Scribus est capable d'importer des fichiers PDF et des fichiers PostScript dans un format vectoriel (donc sans perte) et de les modifier (cela marche mieux avec les fichiers PostScript donc il vaut mieux convertir les fichiers PDF au préalable). Il suffit ensuite d'imprimer le résultat dans un fichier PDF.
C'est un peu lourd mais le résultat est très satisfaisant :
1) au besoin, convertir le fichier PDF en PostScript (ancêtre du PDF)
2) importer le PostScript dans Scribus
3) modifier le fichier avec Scribus
4) imprimer en PDF