Usually, when you have a cloud VPS, you must define on the SIP Settings your public IP address or domain and set the NAT parameter to “Force,Comedia” (Check the attached picture).
Another thing you have to take into account is the network configurations on the phone side, so, if the PBX shows the internal IP address, maybe its because the router is overwritten the SIP headers sent to the PBX. Also, you have to make sure get disabled the “SIP ALG” option on your router (if this option is present).
When you hear the message “There is no route to the destination.” on an incoming call is because you didn’t configure the correct DID. What you have to do in this cases is to check the asterisk console and verify the log output and determinate what is really happening, and why the message is played.