We are looking at changing a USA we look after, and have been told to either use Magento or Shopify.
There's going to be a learning curve to either of them, but Magento has a reputation for being something of a bear to learn. It was built on top of ZF1, though I'm not sure what's at the root of v2.
But here's the issue - we are told the American's don't like paying through PayPal... apparently. Shopify contains the payment processing within itself, whereas Magento and WP Woo Commerce go outside to PayPal/Worldpay and others.
What is the general feeling on this? Is PayPal frowned on now a little, and if it is, why?
People tend to not love PayPal because it's a bit of a pain to integrate and their documentation is pretty bad. There are also issues with vendors not always getting paid or with PayPal nearly always siding with consumers in disputes. Stripe is a much nicer experience on the integration side. I've not personally had much experience with disputes, so I have nothing to contribute there.
We have found most Shopify themes not to be wide screen
You can make your own, so that shouldn't be an issue.