I finally got a signed apk uploaded to Google Play as alpha - great.
However I got stuck with the error:

ERROR: Publisher 'Upload Android APK to Google Play' aborted due to exception: java.lang.NoClassDefFoundError: org/jenkinsci/plugins/tokenmacro/MacroEvaluationException

for a while. No matter what name I entered into the .apk filename row, the above error turned up.
So the reason was the Google Play plugin did not install the required Token Macro plugin. I installed it manually and there I went.