How to cache wp_query with pagination using transients?

You need to set a unique transient key for each page of posts otherwise each page will output same posts.

Here is a example. Focus on get_transient & set_transient functions.

<?php

  $my_posts_query = get_transient( 'my_unique_transient_key_' . get_query_var( 'paged' ) );

  if( false === $my_posts_query ) {

    $args = array( 'post_type' => 'post', 'posts_per_page' => '12', 'paged' => $paged );
    $my_posts_query = new WP_Query( $args );

    set_transient( 'my_unique_transient_key_' . get_query_var( 'paged' ), $my_posts_query, 300 );
  }

  if ( $my_posts_query->have_posts() ) :

    while ( $my_posts_query->have_posts() ) :

      $my_posts_query->the_post();

      // Your loop

    endwhile;

    // This is responsible for 1, 2, 3 pagination links. You can easily change this to previous and nexys links.
    if ( $my_posts_query->max_num_pages > 1 ) :
      $big = 999999999;
      echo '<div class="pagination">';
      echo paginate_links( array(
        'base' => str_replace( $big, '%#%', esc_url( get_pagenum_link( $big ) ) ),
        'format' => '?paged=%#%',
        'current' => max( 1, get_query_var('paged') ),
        'total' => $my_posts_query->max_num_pages
      ) );
      echo '</div>';
    endif;

  endif;

  wp_reset_postdata();

?>