Exclude certain post formats from pagination

You are getting into a bit of a mess by simply skipping posts in the loop if they are not the correct format. You have a couple of options.

Firstly, you can perform the filter using a hook in your theme functions.php. Have a look at pre_get_posts, which allows you to alter the query and remove these gallery posts. Then, in your template you can use the loop and pagination as normal. You can use a check for a specific page or template when applying this hook.

Second option is to call query_posts() in your template or create a new WP_Query to override the main query. You will need to use get_query_var( 'paged') to get the current pagination, for example:

<?php

$paged = (get_query_var('paged')) ? get_query_var('paged') : 1;
$args = array(
    'paged'     => $paged,
    'post_type' => 'post',
    'tax_query' => array(
        array(
            'taxonomy' => 'post_format',
            'field' => 'slug',
            'terms' => array(
                'post-format-gallery'
            ),
            'operator' => 'NOT IN',
        )
    )
);

$query = new WP_Query($args);
?>

<?php if ($query->have_posts()): ?>
    <?php while ($query->have_posts()): ?>
        <?php $query->the_post(); ?>
        // Loop
    <?php endwhile; ?>

    <?php echo paginate_links(array(
        'total'   => $query->max_num_pages,
        'current' => $paged
    )); ?>

<?php endif; ?>

<?php wp_reset_postdata(); ?>

Un-tested code but that should get you started.

Related Posts: