Custom Template 404 for specific custom post type

This is going to track only post_type query var, but you also can add checks for query_vars of all your post_types or only ones you would like to get a custom 404 page for.

add_filter( '404_template_hierarchy', function( $templates ) {
    global $wp_query;

    if ( '' !== $wp_query->get('post_type') ) {
        array_unshift( $templates, 
            sprintf( '%s-404.php', $wp_query->get('post_type') ) );
    }

    return $templates;
});