Find out what the actual performance problem is.
Instrument your applications and measure the response time of each component. A trendy term for these tools is application performance monitoring (APM). Draw a diagram with every detail of how a user's request is served.
Measure from where the users are. Install performance tracking on either the actual user's computers, monitoring points from a cloud or colo facility close to them, or both. Ideally, track when their UI is ready. For web browser based applications, various timing data is available, through analytics packages such as Google Analytics.
Measure the network latency from them to you. TCP or UDP, ICMP is the control plane and possibly not accurate. Canada to France probably is on the order of 150 ms. An unoptimized application that makes, say, 20 requests to do a thing could easily take several seconds.
Get one of those VPN clients and test it yourself, from an affected geography. Compare the latency and traceroute over the VPN versus the internet. Figure out from peering and hops where it transited. The VPN provider may have better connectivity than you do.
All this just to find the problem, solutions could be any number of things. For example:
Add front end web servers closer to the users, such as in North America. Dynamic queries when the database is far away in France adds an additional challenge. Perhaps add a caching tier to the application so data referenced again doesn't need a full query. Or, replicate copies of the database so the queries can be local.
Do not expect "free". Pay for the services you use, so they stay in business and continue to support you.