I've seen paid toilets in train stations (last month in le Mans, a few years ago in a corner of Montparnasse station, though that was before the last round of renovation) and in a mall (CNIT in la Defense). Some RATP train stations have public toilets that you can access with your train ticket, so it's not quite free.