Há muitos posts sobre isso no fórum de ajuda do tex
link
Suas 3 opções não são ótimas, talvez não ajudem. Eu usaria o ghostsscript, mas não sei se ele se encaixa no seu caso.
Estou surpreso que você acertou isso agora. qual versão pdflatex você está usando? As fontes são incorporadas na nova versão do pdflatex ..
No entanto, as fontes podem estar faltando nos arquivos de imagem incluídos. E você conserta esses arquivos separadamente. Por exemplo, se você usar includes de pdf de R, as fontes não serão incorporadas a elas e será necessário corrigir arquivos gráficos, não o documento pdflatex que os contém. Eu consertei isso recentemente com ghostscript. Eu não consideraria qualquer outro caminho.
Suponho que as fontes específicas possam fazer a diferença.
Um exemplo REPRODUZÍVEL é habitual em casos como este. Reúna detalhes e pergunte em tex.stackexchange.
Adicionado em edição:
Aqui está um script de shell que eu uso o ghostscript para inserir fontes em todos os arquivos PDF dentro de um diretório. Eu chamei
embedFontInPDF.sh
#!/bin/bash
## Paul Johnson
## 2013-05-11
##
## R creates pdf files that do not have fonts embedded. This
## uses ghostscript to fix that. It takes all pdf in a directory
## and embeds fonts.
##
## Todo: Make command line argument smarter
for i in *.pdf; do
base='basename $i .pdf';
basenew="${base}/newtemp.pdf"
/usr/bin/gs -o $basenew -dNOPAUSE -dPDFSETTINGS=/prepress -sDEVICE=pdfwrite $i
mv -f $basenew $i
done;