Unable to get paginate_links working with a custom query

I have built a news section in my WordPress site with the advanced custom fields and custom post type ui plugins. On the custom news overview page (not the standard wordpress posts) I wanted to limit the number of news per page to six and provide a navigation with paginate_links. I’ve built the following snippet:

<section class="news-main" role="main">
    <?php
        $args = array(
            'post_type' => 'news',
            'posts_per_page' => '6'
        );
        $the_query = new WP_Query( $args );
        $temp_query = $wp_query;
        $wp_query = NULL;
        $wp_query = $the_query;
        $pagination = array(
            'base' => '%_%',
            'format' => '?page=%#%',
            'total' => $the_query->max_num_pages,
            'prev_next' => True,
            'prev_text' => __( '<< Previous' ),
            'next_text' => __( 'Next >>' )
        );
        if ( $the_query->have_posts() ) : while ( $the_query->have_posts() ) : $the_query->the_post(); ?>
        <article class="news-snippet">
            <header class="news-box">
                <h2 class="mus-hi slogan-head fancy"><span class="fancy-hook"><?php the_time( 'j. F Y' ); ?></span></h2>
                <a href="<?php the_permalink(); ?>"><p class="bran-hn slogan-state closure"><?php the_title(); ?></p></a>
            </header>
            <div class="news-wrap">
                <p class="news-excerpt"><?php echo acf_excerpt( 'news_post', 35, ' <span class="news-more-inbox">[...]</span>' ); ?></p>
                <p class="bran-hn news-more"><a href="<?php the_permalink(); ?>">More &rarr;</a></p>
            </div>
        </article>
    <?php endwhile; ?>
        <?php wp_reset_postdata(); ?>
    <?php else: ?>
        <p>No entries</p>
    <?php endif; ?>
    <nav>
        <?php echo paginate_links( $pagination );
                $wp_query = NULL;
                $wp_query = $temp_query; ?>
    </nav>
</section>

First the arguments for the wp_query are defined, then $the_query is set with a WP_Query afterwards the $wp_query variable is saved into a temporary variable, reset with NULL and then set to the $the_query variable. In the last step the settings array for the paginate_links is set. Then there is the loop for outputting news posts. After the loop the paginate_links function is called and finally the $wp_query got reset and written back the content of the temporary $temp_query variable.

If I have let’s say 15 blog posts my output looks like the following:

If I hover over the number three, the end of the slug looks like the following:

Problem is now the previous and next links are not shown even that they are set. While the main problem is the given slug – if I click the number three I land on a 404 page. “page 3” where I get directed to is unknown for wordpress. Thanks in advance Ralf

Update:

$args = array(
    'post_type' => 'news',
    'posts_per_page' => '1'
);  
$the_query = new WP_Query( $args );
$temp_query = $wp_query;
$wp_query = NULL;
$wp_query = $the_query;
$total_pages = $wp_query->max_num_pages;
if ( $total_pages > 1) {
    $paged = (get_query_var('paged')) ? get_query_var('paged') : 1;
    $current_page = new WP_Query('post_type=news&posts_per_page=1&paged=' . $paged);
    $pagination = array(
        'base' => '%_%',
        'format' => '?paged=%#%',
        'mid-size' => 1,
        'current' => $current_page,
        'total' => $total_pages,
        'prev_next' => True,
        'prev_text' => __( '<< Previous' ),
        'next_text' => __( 'Next >>' )
    );
}

Update 2:

Ok with the following changes to the first part of the code i got the nav working

$args = array(
    'post_type' => 'news',
    'posts_per_page' => '3',
    'paged' => get_query_var( 'paged' )
);  
$the_query = new WP_Query( $args );
$temp_query = $wp_query;
$wp_query = NULL;
$wp_query = $the_query;
$total_pages = $wp_query->max_num_pages;
if ( $total_pages > 1) {
    $the_paged = (get_query_var('paged')) ? get_query_var('paged') : 1;
    $pagination = array(
        'base' => @add_query_arg('paged','%#%'),
        'format' => '?paged=%#%',
        'mid-size' => 1,
        'current' => $the_paged,
        'total' => $total_pages,
        'prev_next' => True,
        'prev_text' => __( '<< Previous' ),
        'next_text' => __( 'Next >>' )
    );
}

The only question i have left (the only thing which is still misbehaving) is it possible that the first link has link instead of link/?paged=1