Luke very helpfully got back to me to sort the problem, but in case it helps anyone else.
The immediate fix is to disable sending the item bag (cart information to PayPal) and using it purely to change the payment amount. But I will attempt to explain in full below.
You disable the cart info being sent to PayPal in your commerce.php settings with:
'sendCartInfoToGateways' => false
Strangely this is the first time we have seen this issue. But it is due to the following in Commerce:
Commerce stores all values in the system in a single base store currency. This means the cart, the discounts, shipping, and anywhere a currency amount is stored is stored as the default base currency.
The payment currency feature is purely designed to allow the charging of the order price in a different currency. The feature allows the customer to know the exact amount to be charged to their card in the currency of their card - without any surprise conversion rate determined by their bank.
Paypal, when it receives the cart information (line item prices etc) is being supplied amounts in that base currency from commerce. Paypal adds up the cart amounts and compares it to the amount that we want to charge the customer in the chosen payment currency. Obviously, the amount we are changing is in the other currency differs from this total.
At first the thought might come as a solution to convert the line items amounts to the other currency for PayPal, but this doesn't work; we do the conversion of the totalPrice of the order for the payment currency feature, and converting each line item and adding them up would usually come up with a different total due to rounding.