With sed which doesn't support non-greedy *, you'd need to use tricks like:
sed 's/_/_u/g;s/|/_p/g;s/<!!!>/|/g
s/===[^|]*|//g
s/|/<!!!>/g;s/_p/|/g;s/_u/_/g'
Or with some sed implementations:
sed 's/<!!!>/\
/g; s/===[^\n]*\n//g; s/\n/<!!!>/g'
To support multi-line matching (as per your edit), with recent versions of GNU sed, you can use the first one with -z option (assuming the file doesn't contain NUL characters) or use something like:
sed ':1
$!{
N
b1
}
s/_/_u/g;s/|/_p/g;s/<!!!>/|/g
s/===[^|]*|//g
s/|/<!!!>/g;s/_p/|/g;s/_u/_/g'
AST-OPEN sed (not commonly found in the wild) supports augmented regexps that support a negation and conjunction operators. There, you can do:
sed -A ':1
$!{
N
b1
}
s/===(.*&(.*\<\!\!\!\>.*)!)\<\!\!\!\>//g'
However, that regexp is quite expensive, so will probably not be usable for large inputs.