You are right there is no filter for this, you would have to hack the global instead, in this case $_wp_registered_nav_menus
:
add_action('after_setup_theme', 'custom_menu_location_label');
function custom_menu_location_label() {
global $_wp_registered_nav_menus;
$find = __('Header Menu'); $replace = __('Something Else');
foreach ($_wp_registered_nav_menus as $location => $description) {
if ($find == $description) {
$_wp_registered_nav_menus[$location] = $replace;
}
}
}