Pandoc is the best tool available to convert markup formats. It supports a lot of formats and you can convert it to any format you want.
If you have a few documents to convert, you can convert them online. You can also install in in your system if you want to convert a lot files. Instructions on how to install on various operating systems is give here.
For ubuntu you can install by
sudo apt-get install pandoc
pandoc readme.md --from markdown --to rst -s -o readme.rst
Pypandoc is a simple python wrapper for pandoc. Using that also, you can convert files.
Install it using pip
pip install pypandoc
output = pypandoc.convert('somefile.md', 'rst')
Update: There is an feature request with pull request to add support for Markdown for PyPi.