I experienced this error message too, and was able to resolve it by using TimeMachine to restore my app's Xcode project file to a version from yesterday.
The provisioning profile issue started today after Xcode 26b3 offered to update my app's project file, and I approved the updates. That update process altered something with the project's provisioning profile data which Xcode 16.4 did not like or did not understand. The result: Xcode 16.4 was unable to install my app on any of my devices (iPad, iPhone, Mac)-- even though Xcode 26b3 was able to.
Prior to making this discovery, I tried most of the troubleshooting tips that you attempted, and none of them worked for me either. It was only after I realized that Xcode 16.4 was able to install my other apps onto my devices, that it dawned on me this issue was confined to a single project. That's when I decided to try restoring the project file from a backup (not the source code; just the Xcode project file).