How to exclude pages in the menu without pageID?

Exclusion has to be based on something connected to the pages that is stored in the database. The only thing template-related stored in the database is the filename of your Parallax template, which is stored in post meta under the key _wp_page_template. You could query for pages that either don’t have the key _wp_page_template, or if it does have the key, that it doesn’t equal whatever the filename of the template file is.

$args = array(
    'post_type'       => 'page',
    'posts_per_page'  => -1,
    'fields'          => 'ids',
    'meta_query'      => array(
        'relation'    => 'OR',
        array(
            'key'     => '_wp_page_template',
            'value'   => 'templates/parallax.php',
            'compare' => '!=',
        ),
        array(
            'key'     => '_wp_page_template',
            'compare' => 'NOT EXISTS',
        ),
    ),
);

You can then use the results of this query to build your own menu rather than using wp_page_menu. This will be more efficient in terms of number of queries, compared to the other option below…

EDIT – Another option is to query for all pages with the Parallax template. You can then use the results of this query to exclude those pages from wp_page_menu:

$args = array(
    'post_type'       => 'page',
    'posts_per_page'  => -1,
    'fields'          => 'ids',
    'meta_query'      => array(
        array(
            'key'     => '_wp_page_template',
            'value'   => 'templates/parallax.php',
            'compare' => '=',
        )
    ),
);

$pages_to_exclude = new WP_Query( $args );

wp_page_menu( array(
   'sort_column' => 'menu_order, post_title',
   'menu_class'  => 'primary-menu',
   'exclude'     => implode( ',', $pages_to_exclude->posts ),
));