Using Raku (formerly known as Perl_6)
~$ raku -e 'slurp.match(:global, / ^^\#+ <-[\#]>* /).sort.join.trim-trailing.put;' file
#OR:
~$ raku -e 'slurp.comb(/ ^^\#+ <-[\#]>* /).sort.join.trim-trailing.put;' file
Sample Input:
####################################
KEY2
VAL21
VAL22
VAL23
VAL24
####################################
KEY1
VAL11
VAL12
VAL13
VAL14
####################################
KEY3
VAL31
VAL32
VAL33
VAL34
Sample Output:
####################################
KEY1
VAL11
VAL12
VAL13
VAL14
####################################
KEY2
VAL21
VAL22
VAL23
VAL24
####################################
KEY3
VAL31
VAL32
VAL33
VAL34
The call to trim-trailing removes the extra \n newline added at the end. If that's problematic either eliminate or use .chop / .chomp instead.