register_nav_menu() function is possible to pass the second parameter inside wp l10n function:
register_nav_menu( 'primary', __( 'Primary Menu', 'theme-slug' ) );
but how to localize the menu items?
Get a WPML plugin - https://wpml.org/
Seriously, get it - it's the most complete solution for multilingual WP site. You can write your own code to translate menu items, but it is not worth it.