Commerce Shipping - arbitrary calculations
I found a module that does exactly what I want: Commerce Shipping Weight Tariff.
I set up three services, one for each destination, and used rules based on the shipping address to work out which service to use. Then I added the weight tariffs for each service.