Descobri que a resposta para ambas as partes da minha pergunta estava aqui: menu Iniciar do Windows 10 faltando certos tipos de atalhos com a resposta aceita.
Basicamente, eu havia fixado o aplicativo que estava mirando com o meu atalho para o menu Iniciar do Windows 10 anteriormente. Por algum motivo, isso impede que o mesmo aplicativo esteja na lista de todos os aplicativos do Menu Iniciar. Tanto a pasta do menu Iniciar do usuário quanto a pasta do menu Iniciar do Windows, em qualquer combinação, farão com que o atalho apareça na lista Todos os aplicativos, de outra forma.