Esta solução corrige todos os títulos certos.
sed -r '
:loop; N; $!b loop
s/\n+(#[^\n]+)/\n\n/g
s/(#[^\n]+)\n+/\n\n/g
s/\n+(#[^\n#]+)/\n\n\n/g
' input.txt;
Com comentários:
sed -r '
### put all file into the pattern space,
# in other words, merge all lines into one line
:loop; N; $!b loop;
### first traversal of the pattern space
# searches the line with "#" sign (all cases matches - Titles, SubTitles, etc),
# takes all its upper empty lines
# and converts them to the one empty line
s/\n+(#[^\n]+)/\n\n/g;
### second traversal of the pattern space
# again, searches the line with "#" sign, take all its bottom empty lines
# and converts them to the one empty line
s/(#[^\n]+)\n+/\n\n/g;
### third traversal of the pattern space
# searches the single "#" sign (Titles only),
# takes all its upper newlines (at this moment only two of them are there,
# because of previous substitutions)
# and converts them to three newlines
s/\n+(#[^\n#]+)/\n\n\n/g
' input.txt
Entrada
text
# Title
## SubTitle
### SubSubTitle
# Title
## SubTitle
text
### SubSubTitle
# Title
# Title
# Title
## SubTitle
### SubSubTitle
Resultado
text
# Title
## SubTitle
### SubSubTitle
# Title
## SubTitle
text
### SubSubTitle
# Title
# Title
# Title
## SubTitle
### SubSubTitle