A criação de um diretório a partir da linha de comando é feita com o comando mkdir ou md .
Como md é um comando interno do interpretador de comandos e não um programa externo, você não pode usá-lo diretamente de start- > executar.
O que você pode fazer é digitar o comando
cmd /c md "\path\to\newdir"
na caixa de comando.
Você pode omitir as aspas se o caminho não tiver espaços.
(Editado: Obrigado pelos comentários úteis)