You can do headings in Markdown like org mode, just use # instead of *:

  # Level 1
  ## Level 2
  ### Level 3
  #### Level 4
  etc.

I rarely see the fiddly format in the wild, probably for the reasons you mentioned, and because it only allows H1 and H2:

  Level 1
  =======
  
  Level 2
  -------

Of course there are lots of things org mode does better than Markdown, I'm just addressing the specific point you mentioned.