In general it should not be a big problem. The built of the menu could be slow, so your best option here is to cache the menus with transient.
if ( !get_transient( 'first_menu_transient' ) ) {
ob_start(); // do not directly output the menu
// build the menu
$first_menu = ob_get_contents();
ob_end_clean();
echo $first_menu;
set_transient( 'first_menu_transient', $first_menu );
} else {
echo get_transient( 'first_menu_transient' );
}
In this way you reduce the databasequeries to a minimum, compared to building the whole menu each time.
To avoid having the wrong menu after changing and saving the menu, delete the transient on the wp_update_nav_menu action.
add_action('wp_update_nav_menu', 'my_delete_menu_transients');
function my_delete_menu_transients($nav_menu_selected_id) {
delete_transient( 'first_menu_transient' ); // you should also just delete the transient of the updated menu, but you get my point - you would have to write the function for linking the menu-IDs to your transient names. For example, just put the ID of the menu in the transient name.
}
Everything clear so far?