Não consigo ajudá-lo com a interface gráfica do usuário, pois atualmente não tenho um computador com o Windows.
Mas todas as interfaces gráficas fazem interface com a linha de comando gpg.exe application (no Linux, OS X e outros sistemas unixoid, você simplesmente usaria gpg ), que você também pode usar diretamente (e para gerando uma chave, o uso definitivamente não é muito complicado).
Abra um prompt de comando. Se bem me lembro, o instalador GPG4Win já define a variável PATH, então você pode executar diretamente gpg.exe de qualquer local. Se você receber alguma mensagem de erro de que gpg.exe não foi encontrado, execute cd C:\Path\To\Your\GnuPG-Folder e execute o comando a partir dali.
Para criar uma chave, use o assistente de geração de chaves, que é iniciado executando gpg.exe --gen-key . Digite os detalhes apropriados sempre que pedir, mas omita a senha (simplesmente pressionando o botão Enter; esteja ciente de que nenhuma saída aparece na linha de comando se estiver digitando senhas!).
A chave gerada na linha de comando também estará disponível em qualquer aplicativo de interface gráfica do usuário.