Thank you for starting this thread. We have just moved to Shopify Plus from WooCommerce but we are struggling with similar issues.
Our main difference between your situation is that we have inventory in each country and so depending on where the customer resides, the products that are in stock would be different. We are not aware of a way for one store to handle this situation and so we will be forced to go with separate stores. (If you know how one store can use different inventories for different geographic locations, I am all ears.)
By the way, we have also been looking at the Shopify Fulfillment Network and were surprised to find out they currently have the requirement that any inventory in their Canada warehouse must be connected with a Canada only Shopify store.