Coloque um atalho no executável em %programdata%\Microsoft\Windows\Start Menu\Programs
e ele deverá se tornar pesquisável no menu Iniciar.
Vale notar que, embora deva se tornar visível imediatamente no menu Iniciar, pode demorar um pouco até que você possa procurá-lo digitando apenas algumas letras.