When an alternative shipping address is provided via the commerce_shipping checkout ui, the shipping address is passed to Paypal Express Checkout instead of the billing address. This causes payments to be declined because the billing address appears to be invalid.
I have not tested the other Paypal payment methods, only Express Checkout. In most other respects, commerce_shipping seems to work correctly for general order processing, so I think that this issue belongs to commerce_paypal.
I have spent a few hours investigating and have been able to verify this on my current build; on a clean install of Commerce Kickstart and also on a bare bones install of Drupal Commerce. In the case of the latter, with only normal commerce sub-modules enabled, together with commerce_shipping and commerce_paypal - screenshots attached.
Steps to reproduce - assuming that Commerce Shipping or Commerce Kickstart is installed and that Commerce Paypal EC is enabled.
Also assumed is that a Paypal Sandbox or Live account is properley configured for Commerce Paypal EC
1. Add an item to the cart and proceed to checkout
2. Provide an alternative shipping address as well as the billing address
3. Proceed to PayPal to pay for the item
I notice that when no shipping address is provided, the shipping address field is automatically populated and I believe that it is this value that is being submitted to Paypal instead of the true billing address.