Это решение исправляет все неверные заголовки.

sed -r '
    :loop; N; $!b loop

    s/\n+(#[^\n]+)/\n\n\1/g

    s/(#[^\n]+)\n+/\1\n\n/g

    s/\n+(#[^\n#]+)/\n\n\n\1/g
' input.txt;

С комментариями:

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\1/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+/\1\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\1/g
' input.txt

Вход

text
# Title
## SubTitle
### SubSubTitle
# Title
## SubTitle
text
### SubSubTitle
# Title
# Title
# Title
## SubTitle
### SubSubTitle

Выход

text


# Title

## SubTitle

### SubSubTitle


# Title

## SubTitle

text

### SubSubTitle


# Title


# Title


# Title

## SubTitle

### SubSubTitle