Abra uma janela de prompt de comando elevada (pressione win + X e, em seguida, pressione A)
Digite "Powershell"
Execute o comando (em uma linha):
Get-AppXPackage -Name Microsoft.Windows.Cortana | Foreach {Add-AppxPackage -DisableDevelopmentMode -Register "$($_.InstallLocation)\AppXManifest.xml"}
Isso deve resolver seu problema.
Fonte: A Pesquisa da Cortana não está encontrando aplicativos no Windows 10