This might work for you (GNU sed):
sed -r '/^PATTERN/!b;:a;$!{N;/^(.*)\n(PATTERN.*)/{h;s//\1/p;g;s//\2/};ba};s/^PATTERN/REPLACEMENT/' file
or another way:
sed '/^PATTERN/{x;/./p;x;h;$ba;d};x;/./{x;H;$ba;d};x;b;:a;x;/./{s/^PATTERN/REPLACEMENT/p;d};x' file
or if you like:
sed -r ':a;$!{N;ba};s/^(.*\n?)PATTERN/\1REPLACEMENT/' file
On reflection, this solution may replace the first two:
sed '/a/,$!b;/a/{x;/./p;x;h};/a/!H;$!d;x;s/^a$/c/M' file
If the regexp is no where to found in the file, the file will pass through unchanged. Once the regex matches, all lines will be stored in the hold space and will be printed when one or both conditions are met. If a subsequent regex is encountered, the contents of the hold space is printed and the latest regex replaces it. At the end of file the first line of the hold space will hold the last matching regex and this can be replaced.