I don't have that option (in Kleopatra, running Linux) under the Tools menu, but it works from the system tray. I have the Certificate imported under "Other Certificates". -snip-
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.


- The User ID is still not certified; Right-click selects Certify...





- Copy the signed message to Text Editor and save it with the file extension * .asc.

- Click the Decrypt/Verify button and select the * .asc file.

- Here are the results:
