Firstly there is a difference in implementation. The above two plug-ins you've linked to save the post in markdown syntax as post meta. WP-Markdown does not do this, but instead converts it back into markdown syntax when you editi the post. Doing it in this way means that it is possible to enable markdown in the comments too.
This plug-in also allows you to enable markdown on your bbPress forums (this was my primary motivation as I wanted an easy way to support code postings on my plug-in support forums and provide a decent UI which brings me onto...).
With both comments and bbPress forums (and if there's demand possibly for posts too), there is a live preview of the generated markdown and a help toolbar. This is exactly what is used on the Stack Exchange websites.
Finally, there is an option to load 'Prettify' which can automatically perform syntax highlighting.
I hope that answers your question. I shall be looking into some more features (processing markdown on only part of the post using shortcodes for instance), and I'm all ears for suggestions!