Coutty, похоже, что они больше не включают в поиск меню Пуск произвольные ярлыки из папки Programs :( Я замечал это на shell:startup и писал фидбэк даже.
Могу предложить такой вариант.
1. Создать в любом месте папку, например, Launch
2. Добавить ее в
пользовательскую переменную PATH
3. В папке Launch создавать жесткие ссылки на исполняемые файлы, которые ты хочешь находить в меню Пуск
Пример
Process Monitor (procmon.exe) лежит в D:\PortableSoft\Tools
В PowerShell (и создание жестких ссылок - это новая фича PS 5.0)
Код:

New-Item -ItemType HardLink -Path D:\Launch\pm.exe -Target D:\PortableSoft\Tools\procmon.exe
Заметь, что для жесткой ссылки можно указать любое имя исполняемого файла.
Альтернатива -
AppPaths в реестре