Is it possible to set up a payment method based on the shipping?

I have a site that does free shipping to UK and accepts PayPal, I have the shipping method based on 2 zones which are 'UK' and 'International' I also have the payment setup the same way. They could have free shipping to UK and pay with PayPal if they were in the uk. If they are in ANY other country it shows shipping method as 'request shipping quote' and then payment is a modified COD which also says 'request total with shipping quote'. That way orders with an international address can't pay using PayPal because they wouldn’t have no shipping costs to go with the cost of the product.

The above works fine until a customer in an international destination wants to send a package to the UK. It allows them to pick free UK postage but doesn’t show PayPal as a payment method because the billing address is international.

So what I need to be able to do is show paypal as a payment method as long as the shipping address is UK.

Does anybody know if this is possible? If so, how would I achieve this please.

Any help would be much appreciated.

Thanks in advance
Huw