O Gimp que está disponível na maioria das distribuições Linux pode fazer isso facilmente.
sudo aptitude install gimp
Em seguida, abra um PDF, selecione uma área, Ferramentas > Transformar ferramentas > Escala. Quando terminar, exporte como PDF.
UPDATE: Se você se importa com a importação de PDFs ehile preservando sua estrutura vetorial, você pode usar o Inkscape.