Just ran into this issue as well on Visual Studio Pro 16.8.2. Waiting 12 hours didn't do it for me. I also noticed that the Microsoft Store app was in a hung state - several app updates were wedged in "Installing..." but with no progress. Here's what I did to get unblocked:
Reset Microsoft Store
- Open the Settings app and navigate to Apps
- Search for "Microsoft Store in the list and click it, then click "Advanced Options" that appears after clicking the app
- Scroll down and click the "Terminate" button
- Scroll down and click the "Reset" button - agree to the prompts that appear
- Open an admin command prompt
- Run wsreset.exe
After wsreset.exe completes, I restarted my computer. When it came back up, I installed all of the Microsoft Store app updates, which included an App Installer update, which is probably important, but that's mostly speculation. After all the store apps updated, I opened VS and went to deploy my UWP. It hit the same point as before where it said it needed to install the appx, and then quickly blew through it and deployed the app.
All of these steps may not be necessary, but it's what I did to get unblocked. Hopefully, it helps someone else.