Page template added via plugin not saved in Gutenberg

(Revised answer)

Gutenberg (or the Block Editor) uses the WordPress REST API when working with a Page/post (creating, updating, etc.) and the REST API will check whether the template is valid for the given post through WP_REST_Posts_Controller::check_template() and when the template is not valid, the error template is not one of will be thrown.

And as I (recently) stated in this answer:

By default, is_admin() returns false on a REST API endpoint/URL. So if for example you’re on http://example.com/wp-json/wp/v2/posts (or that you make API request to that endpoint), then:

if ( is_admin() ) {
    // code here does **not** run
}

So that should answer the question, where in your wpte_add_destination_templates function, the is_admin() check fails and the custom template is not added to the list of valid/registered templates; and eventually results in the error template is not one of.

Possible Solutions

Hook to both wp_loaded and rest_api_init

add_action( 'wp_loaded', array( $this, 'wpte_add_destination_templates' ) );     // for admin requests
add_action( 'rest_api_init', array( $this, 'wpte_add_destination_templates' ) ); // for REST requests

And in the wpte_add_destination_templates function:

// If REST_REQUEST is defined (by WordPress) and is a TRUE, then it's a REST API request.
$is_rest_route = ( defined( 'REST_REQUEST' ) && REST_REQUEST );
if (
    ( is_admin() && ! $is_rest_route ) || // admin and AJAX (via admin-ajax.php) requests
    ( ! is_admin() && $is_rest_route )    // REST requests only
) {
    add_filter( 'theme_page_templates', array( $this, 'wpte_filter_admin_page_templates' ) );
}

Or hook directly to theme_page_templates

//add_action( 'wp_loaded', array( $this, 'wpte_add_destination_templates' ) ); // remove
add_filter( 'theme_page_templates', array( $this, 'wpte_filter_admin_page_templates' ) );

And then your wpte_filter_admin_page_templates would be:

function wpte_filter_admin_page_templates( $templates ) {
    // If it's an admin or a REST API request, then filter the templates.
    if ( is_admin() || ( defined( 'REST_REQUEST' ) && REST_REQUEST ) ) {
        $templates['templates/template-destination.php'] = __( 'Destination Template','' );
    } // else, do nothing (i.e. don't modify $templates)

    return $templates;
}