A maneira mais fácil de fazer o que você quer é modificar o documento original e recriar o documento a partir dele. PDF é uma linguagem de descrição de layout de página. Por tudo que você sabe, o arquivo pode nem ter o símbolo incorporado, mas apenas uma representação gráfica dele. (Observe, no entanto, que o visualizador do Acrobat faz um bom trabalho de "adivinhar" um símbolo de uma fonte instalada se um arquivo contiver um glifo que não esteja incorporado nem instalado no sistema.)
Se você não puder alterar o arquivo original, alguns programas poderão permitir que você faça a alteração. O Acrobat Pro deve conseguir. (Do que você escreveu, eu não sei porque suas tentativas falharam.)
Se não, você terá que alterar o arquivo programaticamente. (E é aí que o stackoverflow.com entra) Você pode fazer isso usando a API do Acrobat ou alguma outra API comercial proprietária, ou você pode tentar usar algo como o pdftk. (Eu não fiz nada e não posso mais ajudá-lo com isso.)
Note que, geralmente, o mais fácil é alterar o documento original.