Could this be related to the change of itinerary I made on my last trip?
No, this seems exceedingly unlikely. Schengen countries do not consolidate or share this information. Furthermore, even the data that is shared is not kept forever and I think 5 years is often the default expiration date (thinking of SIS alerts for example, although they can be renewed).
Even countries that do collect data on entries (e.g. based on passenger manifests / APIS or document scans at the border) will inevitably have a partial record sitting on the systems of the border force. I seriously doubt each and every Schengen country (and especially France) has built systems to make it effectively usable in consulates or staffed them to routinely analyse past travel patterns (which is a lot of very messy data). I have read many comments from people who seem to believe it ought to be that way but this is just not how this works.
The only way in which it could matter is if some official noticed the change at the time and deemed it serious enough to act on it. For example, if you somehow got a fine and a ban following a police check of some sort or maybe during the exit check. In that case, there would in fact be a record and it could easily lead to a refusal (but with another justification than the one you got). Obviously, you would probably have noticed if something like that had happened.
Do I risk to get rejected if I apply for tourist visa in a different Embassy?
That’s much more risky. The refusal is still fresh and much more relevant than any potential small violation five years ago. A record of your earlier application is actually shared between Schengen countries using the exact same system the other consulate will have to use to track your new application (it's called the VIS and it will contain a record of the refusal, which is also kept for 5 years by default). When examining any new application, the consular officer is bound to notice and take that into account.
And it doesn’t look good: It suggests that you are trying to circumvent the earlier decision and might not be completely sincere in your wish to visit any of these countries but rather looking for a consulate that will issue a visa and ready to tell them anything to get that.