Update Oct. 2018, as commented below by PHPirate:
λ git --version
git version 2.19.1.windows.1
λ gpg --version
gpg (GnuPG) 2.2.9-unknown
libgcrypt 1.8.3
Copyright (C) 2018 Free Software Foundation, Inc.
No trace of that update in git-for-windows/git/releases
Original answer (2017):
By default, Git for Windows includes a gpg1, not gpg2
vonc@bvonc MINGW64 ~/.ssh
$ gpg --version
gpg (GnuPG) 1.4.21
Using a different gpg is indeed recommended:
git config --global gpg.program "c:/Program Files (x86)/GnuPG/bin/gpg.exe"
Try again with the latest Git for Windows with UTF-8 set in locale.
Try a Git simplified path to rule out any interference from other programs.