Both mp4 and mkv file formats are containers which contains media streams(subtitles, audio, video, chapters), not codecs. If you have some mkv files just demux them and remux again as mp4. Converting instead of remuxing mkv to mp4 is waste of time and also quality degradation.
Well, that depends on the type of audio in the file. If you use DTS, you'll need to have the audio reencoded. Use something like MKV2VOB though, and it'll do that on the fly (if necessary), giving you an .mpg file that the Surface can play in the end.
I still want to see a video player for Windows RT that can handle MKV (including DTS audio, subtitle support, etc.) but this will do for now.