How to Implement Modal AJAX Form Pagination
To implement this I went down a similar route as the "Add another item" functionality on field api fields. For reference, this is done in WidgetBase.php.

Firstly, I copied over a couple of static functions to get and set values inside storage:

/**
 * {@inheritdoc}
 */
public static function getModalState(FormStateInterface $form_state) {
  return NestedArray::getValue($form_state-&gt;getStorage(), ['search_results']);
}

/**
 * {@inheritdoc}
 */
public static function setModalState(FormStateInterface $form_state, array $field_state) {
  NestedArray::setValue($form_state-&gt;getStorage(), ['search_results'], $field_state);
}


Then in buildForm() I added this to intialise the storage if it wasn't set yet.

if (!static::getModalState($form_state)) {
  $field_state = array(
    'page' =&gt; 1,
  );
  static::setModalState($form_state, $field_state);
}


And then use the storage to get the page parameter for my search:

$modal_state = static::getModalState($form_state);
$page = $modal_state['page'];
$search_response = $this-&gt;getSearchResults($page);


The crucial part of the implementation was separating the increment in the page variable from the ajax handler and putting it into the submit handler. So for the "Next" button:

// Add "next page" pager.
$form['next'] = [
  '#type' =&gt; 'submit',
  '#value' =&gt; $this-&gt;t('Next'),
  '#submit' =&gt; ['::nextPageSubmit'],
  '#ajax' =&gt; array(
    'callback' =&gt; '::searchAjax',
    'wrapper' =&gt; self::AJAX_WRAPPER_ID,
    'effect' =&gt; 'fade',
  ),
];


And the submit handler

/**
 * Submission handler for the "Next page" button.
 *
 * @param array $form
 *   The form.
 * @param FormStateInterface $form_state
 *   The form state.
 */
public function nextPageSubmit(array $form, FormStateInterface $form_state) {
  // Increment the page count.
  $modal_state = self::getModalState($form_state);
  $modal_state['page']++;
  self::setModalState($form_state, $modal_state);

  $form_state-&gt;setRebuild();
}


My ajax callback is then the same for searching, and paginating.

I also added a submit handler to the search button to reset the page back to 1.

The full source code for the form in this state can be found at https://github.com/acbramley/embridge/blob/2a561c9c388ccf715f93727cf136e50fc02163c9/src/Form/EmbridgeSearchForm.php

These code snippets are essentially the guts of what I needed to get the pagination working.