Seems that the query string is coming from the base argument call to get_pagenum_link()
so I have removed the query string component and re-add it with ‘add_args’. Like so:
<?php echo paginate_links(array(
'base' => preg_replace('/\?.*/', "https://wordpress.stackexchange.com/", get_pagenum_link(1)) . '%_%',
'current' => max(1, get_query_var('paged')),
'format' => 'page/%#%',
'total' => $wp_query->max_num_pages,
'add_args' => array(
's' => get_query_var('s'),
'post_type' => get_query_var('post_type'),
)
)); ?>