How to add query vars with paginated URLs?

Use the add_args parameter to add an array of query string arguments to pagination links:

  echo paginate_links( array(
    'base' => add_query_arg( 'cpage', '%#%' ),
    'format' => '',
    'prev_text' => __('«'),
    'next_text' => __('»'),
    'total' => ceil($total / $items_per_page),
    'current' => $page,
    'add_args' => array(
        'category' => 'fruit',
        'color' => 'red'
    )
  ));