How should I convert Markdown (or similar) to a Word Document?

Get pandoc version 1.9 or higher. Then:

pandoc myfile.txt -o myfile.docx

Recent versions of pandoc allow direct conversion of markdown to word.

This isn't a complete answer to your situation, but you may want to investigate using Pandoc which can convert Markdown into other formats including RTF (which MS Word should be able to handle reasonably well).

Unfortunately, I have no idea if this will work with the DeepFreeze system you describe.

If you already have a Markdown tool for producing HTML, open the HTML in a browser and copy/paste into Word. Alternately, just open the HTML file itself in Word then save as Word format.