How do I add a new program to the Start Menu?

So the pattern seems to be this:

If you have ever pinned a shortcut to start, then any shortcut later created to the same target, will also be pinned.

One solution: rename or relocate the shortcut's target.

For example, I had previously pinned a shortcut to VNC, so I couldn't get it to appear in All Apps. I renamed VNC-Viewer-5.2.3-Windows-64bit.exe to vnc 5.2.3.exe, and shortcuts created to it in Programs now appear in All Apps, instead of pinned.

Shortcuts to never-before-pinned targets, or renamed targets, will show up in All Apps. You may have to restart to see them, but they will show up.

Unfortunately, you don't seem to be able to unpin a shortcut in the sense of removing this association. Instead, unpin simply removes the shortcut, and if you put it back, that is treated as 'turning the pin back on'. I infer that there is a database of 'should be pinned' targets, located here:

C:\Users\Saber\AppData\Local\TileDataLayer\Database\vedatamodel.edb

I don't know any easy way to edit that, though. Perhaps if you used a hex-editor to change a letter in the target path in that file, it would fix it.

Other posters have suggested overwriting the entire TileDataLayer folder with a copy from a clean windows user, however that seems a bit dodgy to me.