While I (thankfully) haven't had to write Markdown from my phone, I think this is might be worth exploring. I have very similar experiences trying to find common programming symbols in the Google keyboard on my Pixel.