Pagination showing same posts despite changing page

After struggling for hours on this (and 6 years after the question was asked), for me the solution was lying within the $paged parameter:

I changed

$paged = ( get_query_var('paged') ) ? get_query_var('paged') : 1;

to

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

And then it worked!