Eu acredito que o markdown espera o Unicode. talvez você possa tentar usar o recode para alterar a codificação de sua codificação padrão para UTF8.
De acordo com o manual markdown2pdf da Pandoc
Input is assumed to be in the UTF–8 character encoding. If your local character encoding is not UTF–8, you should pipe input through iconv:
iconv -t utf-8 input.txt | markdown2pdf
markdown2pdf assumes that the unicode, array, fancyvrb, graphicx, and ulem packages are in latex’s search path. If these packages are not included in your latex setup, they can be obtained from http://ctan.org.
Admito que, apesar de eu usar indiretamente o LaTeX, muitas vezes eu acho que é difícil entender e usar as mensagens de erro e de aviso. Assim, embora o acima pareça um caminho promissor, pode ser um beco sem saída.
Outra possibilidade é testar o markdown em conjunto com o htmldoc de Markdown2pdf do Pandoc - Eu não sei se vai resolver o problema, mas pode valer a pena tentar.
Eu não estou recebendo as mesmas verificações que você
$ wget -O Cyrillic2.markdown.txt http://paste.ideaslabs.com/download/J58n5B6cGp
11:06:08 (20.53 KB/s) - 'Cyrillic2.markdown.txt' saved [4078/4078]
$ sum Cyrillic2.markdown.txt
40224 4 Cyrillic2.markdown.txt
$ cksum Cyrillic2.markdown.txt
3250703884 4078 Cyrillic2.markdown.txt
$ openssl dgst -sha1 Cyrillic2.markdown.txt
SHA1(Cyrillic2.markdown.txt)= e1d6d92b5c7a3c8673ab5dff4bfe01628b17d77a