maybe this is usefull for anyone, who needs an easy solution without changing functions:
I just replaced the links via regular expressions AFTER including in the template. This snippet is only working for 2 levels, but is easily changed.
<?php
$menu = wp_page_menu(array('sort_column'=>'menu_order','echo' => 0));
$menu = preg_replace("#".site_url()."([^\"]+?)/(.+?)#i", site_url()."$1#$2", $menu);
echo $menu;
?>