Нашёл решение для моих случаев:
gs -sDEVICE=pdfwrite -dNOPAUSE -dBATCH -dSAFER -sOutputFile=output.pdf input.pdf
После этого у output.pdf невероятным образом появляется верная кодировка.
В Windows исполняемый файл должен называться gsw32c, gswin32c, или тоже gs.
