Je crois que toutes les méthodes qui traitent du pdf font appel en sous-main à ghostscript (y compris l'imprimante), donc reviennent à la commande évoquée en #10. Pour améliorer la qualité des images, il suffit de d'ajouter -r300 à la commande pour qu'elles soient en 300dpi. Par défaut elles sont en 75dpi.
gs -sOutputFile=biniou.pdf -sDEVICE=pdfwrite \
-sColorConversionStrategy=Gray -dProcessColorModel=/DeviceGray \
-r 300 -dCompatibilityLevel=1.4 Plot.pdf < /dev/null
Avec convert, ajouter l'option -density 300 devrait produire un rendu équivalent. Si ce n'est pas suffisant, on peut préférer une densité de 600dpi.
edit: J'ai testé, même avec l'option -density, convert renvoie des images dégradées. Il vaut mieux adopter la première méthode.