Recently I tried Kleopatra version 3.0.1 on Ubuntu 18.04.5 LTS and managed to verify the message.
Maybe the following methods worked for you too:
- Copy the Public Key into Clipboard.
- At Kleopatra, click the Clipboard button, select Certificate Import.
I have a different version, and it's asking me for my password when I try to Certify Certificate. The ones I tried don't work, or it doesn't even tell me they're wrong, it just says it can't be certified.
I'm amazed how complicated verifying a PGP message is, compared to how easy it is to verify a Bitcoin signed message.