For what it's worth I figured I'd post my solution,
What ended up working for me was close to what you were recommending. I had to create a custom logon task in the User Environment portion of DEM that pointed to a powershell script that contained this:
Set-ExecutionPolicy Unrestricted
Add-Appxpackage -register "C:\Program Files\WindowsApps\Microsoft.WindowsCalculator_10.1805.1201.0_x64__8wekyb3d8bbwe\AppxManifest.xml" -DisableDevelopmentMode
Essentially, that command can be run for any of the UWP apps you experience the issue with, just have to substitute the correct app name for the one you're dealing with. Once you have that, you can place that powershell script on any network location, head over to DEM and create a Logon Task like this:
Once the user logs in, the icon for the UWP app should be there and should launch without issue. Not necessarily the cleanest way to remedy the problem, but it works. These UWP apps are an absolute pain to deal with in Horizon...
Thanks for your recommendation. I'll mark you for a correct answer.