After going rounds and rounds, we found the issue yesterday.
So, the story is this - I kept getting the upgrade alert from PAD and I tried doing the update from the Power Automate Cloud. Nothing happened. I uninstalled the PAD. Went through the Microsoft Store route and reinstalled the PAD from there. I got the upgrade. It worked until I ran into a problem with adding the PAD action into my cloud flow.
After uninstalling/reinstalling, deleting machine, renaming the machine, deleting the duplicate PAD icons, the list goes on, everything failed. We went into the local app data folder and noticed there were two folders. Old version and the new version. We deleted these two folders, cleared out the cache. And then reinstalled the current version of PAD via Power Automate Cloud and now it works.
Interesting to note, when installing the PAD from Microsoft Store, it will create another PAD. It doesn't even communicate with the Power Automate Cloud PAD. It doesn't even delete previous versions. Nothing. And to upgrade the current version of PAD via Power Automate Cloud, it doesn't even delete older version, either.
This is definitely a Microsoft issue.

