@Jackgruz , you should be able to move custom domain from one web app to another even under same App Service plan. 404 error indicates the site is not reachable. Have you deleted the custom domain first and trying to add to new web app? If so domain verification process would take 48 hrs. In some cases, it extends beyond that. I suggest you wait for few hours for the propagation to occur.
Also, check if your custom domain is a root domain then you need to add only A record to your registerer site instead of CNAME. CNAME for root domain is not yet available for web app custom domain feature.
----------
Please do not forget to "Accept the answer" wherever the information provided helps you to help others in the community.