Anything that secures the connection will do.
The most compatible option using a layer 2 or 3 VPN to connect the two systems (and firewall them properly against anything else): unless you're dealing with a really, really strange protocol, you're pretty much guaranteed to be able to make it work. The downside is that it can be delicate to configure that on cloud-based hosts and it doesn't scale well.
The second option, as you guessed, is to use TLS connection between machines, That will depend heavily on what software you're using but TLS is a pretty common option and you can usually configure it for mutual x509 certificate authentication which will give you a pretty good level of security. Note that all HTTP-based RPC will be able to use TLS and that forcing mutual authentication is typically a matter of configuration.
The third option is to enable encryption inside the message broker architecture. Contrary to what you wrote, many message broker system will allow you to configure end-to-end encryption at the message level. It's usually not really trivial to implement, however. for instance, take a look at WebSphere's help page on that subject. The main advantage of that option is that messages are encrypted at rest as well as in transit and that means the message queue system doesn't have to be able to decrypt the messages themselves: all it requires i^s the correct enveloppe data.