Como o @steeldriver aponta, é fácil se você tiver regexps não-gananciosos. Se não, você pode fazer isso com um loop, assim:
sed ':a;s/PATTERN-2/\n/;s/PATTERN-1.*\n//;ta' test.txt
Isso funciona porque sabemos que não há novas linhas no meio de nenhuma linha. Funcionaria também com qualquer outro caracter que não ocorra em qualquer linha, por ex. §
.