Filter 'wp_nav_menu_objects'
. You get an array as argument, a list of all items.
Pseudo-code, not tested:
add_filter( 'wp_nav_menu_objects', 'wpse_76401_filter' );
function wpse_76401_filter( $items )
{
$out = array();
foreach ( $items as $item )
{
if ( isset ( $item->url ) )
$item->url = add_query_arg( 'variable', '123', $item->url )
$out[] = $item;
}
return $out;
}