Hi Olivier,
The same with the process of creating content / modules ... in a multilingual Joomla site, you need to duplicate template styles and set default style for each language.
Here are steps that you can follow:
1/ Create menu for each language (it seems you did it already)
2/ Duplicate template style for each language
3/ Under Navigation settings of each language, clone the default navigation profile and assign associated menu of that language to this profile:

For example, you have 1 template style for English >> duplicate the default profile to have a new one: default-en then assign the menu-en menu to this profile.
It will work.