Hi Geraldine
A client of ours used http://www.regus.fr/ to set up an address in Paris for this purpose and later opened a real office - and a real French company - when sales increased. Regus have offices worldwide see http://www.regus.fr/country-selector.aspx so I imagine that they can help for all countries.
I'll add to Gianluca's comments that Google won't be "fooled" by this address into recognising you as a French company. Google checks this through access to company registration databases rather than its own My Business listings.
But there are plenty of other advantages in having a My Business listing and Paris would be a good base in France for your site (audience reach). For an e-commerce site, potential clients will be reassured by a local telephone number too.
Looking at the French site, I noticed that the HREFLANG is incorrectly implemented. This is more important than the postal address. I strongly suggest you correct that
- Neil