Why (and how?) is get_header() erasing all my stuff?

There is most likely an issue of load order. The get_header() function does included your header.php file, so I’m not sure what’s happening inside that template. One way to figure out is to include it using include() and check if the behavior is the same.

I would suggest you hook into the wp_head or init and define your constant there.

add_action('init', 'define_my_constant' );
function define_my_constant() {
    if ( ! defined( 'CUSTOM_MENU' ) && is_page() ) {
        define('CUSTOM_MENU', '<ul><li>Test</li></ul>');
    }
}

init is one of the earliest hooks that runs on WordPress, so your constant should be accessible in any theme or plugins at that point.