Sed: within the same line, stop repeating pattern replacement once a certain string is reached

You could replace one at a time in a loop, until there are no more CATs before the STOP:

$ echo 'two CAT two four CAT CAT seven one STOP four CAT two CAT three' |
    sed -e :a -e '/CAT.*STOP/s/CAT //;ta'
two two four seven one STOP four CAT two CAT three

With any awk:

awk '{while($0~/CAT .*STOP/)sub(/CAT /,"")}1' file

$ echo 'two CAT two four CAT CAT seven one STOP four CAT two CAT three' |
  awk '{while($0~/CAT .*STOP/)sub(/CAT /,"")}1'
two two four seven one STOP four CAT two CAT three

With perl

perl -pe 's/CAT (?=.*STOP)//g'

this will replace CAT only if there is STOP is present later in the line