I thought this had been discussed thoroughly in the past already, but I’ve only found threads that consider one detail or another, e.g. flower boxes and fully boxed headings.
Equals sign = and hyphen-minus - underlines must remain top and second level, respectively, for compatibility with existing content and parsers.
Tilde ~ underlines cannot work because they are used for code block fences, likewise grave accent `.
It might be possible to reuse the hash mark #, but its role in ATX heading prefixes (and optional suffixes) makes it prone to bugs and misunderstandings.
Variant 1
Reusing the other two allowable characters from thematic breaks, which are also visually horizontal lines in code (and possibly presentation), seems like a sensible approach. They are asterisk * and underscore _. Since they are also the affix characters used to delimit inline emphasis, there is a certain possibility of mistreatment in legacy implementations. As asterisk is a tad stronger than underscore in flanking behavior, I’d see it as the higher level. This also agrees with other lightweight markup languages, where * is boldface / strong emphasis and _ is italic / normal emphasis. The counter argument would be that the underscore at least is a horizontal line like the existing ones.
Other ASCII punctuation that would be available and looks acceptable, are the plus sign + and the circumflex ^. The former is already used as a line marker for bullet list items alongside - and *, the latter is only used by extensions yet (e.g. for superscripts).
H1
===
H2
---
H3
***
H4
___
H5
+++
H6
^^^
Variant 2
The underscore looks particularly misplaced, in my opinion. Every punctuation mark that’s graphically located (mostly) on the base line will, e.g. period . or comma ,. The only other ones located at the top of the glyph box, are the replacement quotation marks " and apostrophe '. If authors use enough of those in a sequence, it actually looks like an underline.
H1
===
H2
---
H3
^^^
H4
"""
H5
'''
H6
***
(I’m more open to an alternative order of levels in this variant.)