Turns out that there is just a small change to the way the pagination links need to be written out.

page/ needs to be prefixed to %#%

Corrected example below.

Hope this helps someone with the same issue in the future.

<?php // Pagination
  echo paginate_links( array(
    'base' => get_permalink() . 'page/%#%' . '/#gallery',
    'format' => '?page=%#%',
    'current' => $page,
    'total' => $pages
  ) );
  ?>

Turns out that there is just a small change to the way $page variable is set and the way the pagination links need to be written out.

the variable of page needs to be updated to paged and in the pagination array

page/ needs to be prefixed to %#%

Corrected example below.

Hope this helps someone with the same issue in the future.

if( get_query_var('paged') ) {
  $page = get_query_var( 'paged' );
} 

<?php // Pagination
  echo paginate_links( array(
    'base' => get_permalink() . 'page/%#%' . '/#gallery',
    'format' => '?page=%#%',
    'current' => $page,
    'total' => $pages
  ) );
  ?>