Thanks for reaching out. I did quick test to connect the HiveMQ cloud cluster Using MQTT CLI. I have followed steps mentioned at Quick Start Guide.
If it is feasible, please do a quick test if you can connect the HiveMQ Cloud with MQTT CLI. You may need to contact Paho mailing list to get this issue resolved if you can connect broker using MQTT CLI.