A solução mais fácil e rápida que segue seu método é iniciar o prompt de comando da seguinte maneira:
Pressione win para abrir o menu inicial. Digite cmd
para procurar por Prompt de Comando.
Pressione ctrl + desloque + entre para iniciar o Prompt de Comando como administrador.
Isso funciona no Windows 7 e superior.
O win + r não suporta nativamente isso, mas uma maneira alternativa (e menos rápida) é digitar runas /user:Administrator cmd
e depois digitar a senha para a conta do administrador.
EDIT: Parece que a versão mais recente do Windows 10 oferece suporte para ctrl + deslocamento + enter na caixa de diálogo Win + R , então agora você pode usá-lo também.