Solution 1:

App aliases are stored in %USERPROFILE%\AppData\Local\Microsoft\WindowsApps

This can be verified using the where command:

C:\Users\Daniel>where spotify
C:\Users\Daniel\AppData\Local\Microsoft\WindowsApps\Spotify.exe

By default, this is the single entry in the per-user %PATH% environment variable:

enter image description here

(Only had a German VM with a clean account at hand.)

If, for whatever reason, this entry is missing, you can easily add it again. Remember to add it to the “User variables” section’s %PATH% variable (usually visible as “Path” in the list). Some program installers mess with this list to add themselves to it. It doesn’t always end well.