I do some similar things (put shortcuts in the start menu for quick "Win+S..type name (or few chars) of shortcut..press enter" ways of loading programs and scripts). I haven't noticed any problems with the new update, but here are a couple of things I would try in your case:
1) Make a backup of the folder that contains your shortcuts. Delete it and restart the computer. Then copy it back in (and possibly rename it). The thinking here is it might help the search index to rebuild itself.
2) Add the folder to your PATH. Here is a link on how to do it if you need to know how: How do I set system environment variables in Windows 10?
As of Win 10 (1903) Aug 2019, it seems that the Start Menu will now allow duplicate shortcuts to the same .exe as long as the arguments are different. For this to work though, the "duplicate" shortcuts needs to be created by any method OTHER THAN making a copy of the already existing shortcut in the Start Menu and modifying it.
So, a shortcut created with the target as
C:\Windows\system32\cmd.exe /K "cd C:\"
will open up the command prompt at C:\, and a shortcut created with the target as
C:\Windows\system32\cmd.exe /K "cd C:\Users\"
will open up the command prompt at C:\Users\. Both shortcuts will be shown on the Start Menu, in addition to the default Command Prompt shortcut, even if they have the same name.
I was also able to create a duplicate shortcut to cmd.exe that will show up in the Start Menu and function identically by using ' as an argument. Target:
C:\Windows\system32\cmd.exe '
Which I can then modify to launch cmd with different properties (admin/compatability etc.). This may not be suitable for other executables.
Best Answer
The startup folder is still there and functions as normal.
To access it, press Windows+R, then type
shell:startup.You should be able to do what you were previously doing in Windows 7 from there.