A solução mais fácil e rápida que segue o seu método, é iniciar o prompt de comando da seguinte forma:
Prima win para abrir o menu Iniciar. Digite cmd
para procurar pelo prompt de comando.
Pressione ctrl+shift+enter para iniciar o prompt de comando como administrador.
Isto funciona a partir do Windows 7 e superior.
win+r não suporta isto nativamente, mas uma forma alternativa (e menos rápida) é digitar runas /user:Administrator cmd
e depois digitar a senha para a conta do administrador.
EDIT: Parece que a última versão do Windows 10 oferece suporte para ctrl+shift+enter na caixa de diálogo Win+R, então agora você pode usá-lo lá também.