Pressionando a tecla do Windows e "S" ao mesmo tempo, abrirá o thingie do recurso de pesquisa do Windows 8. Você provavelmente está pressionando a tecla Windows com o pulso ou outro dedo, ou o teclado tem uma falha como pressionar S para que pareça que a tecla do Windows também é pressionada.
Você pode tentar usar um teclado USB para descartar problemas físicos com o teclado?