Rename the label on a menu location which is already defined?

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;
        }
    }
}