Understood. Converting the first image attachment into a featured image is straight forward and yields consistent results, but not necessarily optimal results. Removing the img tag and possibly associated caption shortcode can get a bit tricky. Besides the expected search and replace strategy, you need to be sure you are removing all content between the correct tags. Finding the correct closing tag is not always that simple, as tag delimiters may occur in caption content.
You also need to ensure the img tag relates to the attachment that was converted. Just because it was the first attachment, it may no longer be the first img tag encountered. It may also possibly occur more than once for some reason.
IMHO, this is not a coding issue, it is human resource issue. As such, you should not code a fix, you should manage your resources. A coding fix only encourages non-compliance since the software fixes the transgression anyway.
Perhaps non-conforming posts should be rejected upon submission, forcing the author to assign a featured image in order to successfully submit their post. They could of course then assign the featured image without removing it from the content, but this condition is easier to scan for than it is to fix by code. The presence of a featured image URL in content could throw a warning on submission.
I of course know nothing of your circumstance, so this alternate approach may be completely unworkable. But it could also lead to yet another approach, so I’m throwing it into the ring anyway.