There is a multilang filter available, for just this purpose. It would take some testing, but the multilang filter does work with your scenario, if you follow the instructions in Site administration > Appearance > Theme settings > Custom menu items.
The correct order of things in your custom menu would be:
Display name|url|Title for mouse over|language
That should do the trick.