How to start a new post with custom Taxonomies already set?

You can use the transition_post_status action for that. New posts transition from new to auto-draft, so we check for that condition to only add terms on that initial auto-save.

function wpd_add_post_terms( $new_status, $old_status, $post ) {
    if( 'new' == $old_status && 'auto-draft' == $new_status ){
        wp_set_post_terms( $post->ID, array( 42, 23 ), 'category' );
    }
}
add_action( 'transition_post_status', 'wpd_add_post_terms', 10, 3 );