This is how I override the WordPress search page to implement better results thanks to Relevanssi:

global $wp_query;
        $search_txt = get_query_var('s');    
        $args = array(
          's' => $search_txt,
          'post_type' => 'formations',
          'posts_per_page' => 9,
          'paged' => $wp_query->query_vars['paged'], // conserver le numéro de page de la requête initiale
        );

        // filtrer suivant la bonne taxonomy
        if (isset($_GET['taxonomy'])) {
          switch ($_GET['taxonomy']) {
            case 'formation-diplomantes-cpf':
              $ta = ['formation-diplomante', 'formation-eligible-au-cpf'];
              $op = 'AND';
            break;

            case 'toute-formation':
            break;

            default:
              $ta = $_GET['taxonomy'];
              $op = 'IN';
          }

          if (isset($ta)) {
            $tq = [[
              'taxonomy' => 'type_form',
              'field'    => 'slug',
              'terms'    => $ta,
              'operator' => $op,
            ]];// Tax Query

            $args['tax_query'] = $tq;
          }
        }

        $fq = new WP_Query();
        $fq->parse_query( $args );

        relevanssi_do_query($fq);

        $any_formation  = false;
        $fdia           = [];// Formations DIOGEN IDs Array
        $fia            = [];// Formations IDs Array
        $i=0;
        while ($fq->have_posts()) : $fq->the_post();
          if ( 'formations' == get_post_type() ) { 
            $i++;
            $fdia[get_the_ID()]     = get_field('id_diogen', get_the_ID());
            $fia[]                  = get_the_ID();
            $any_formation      = true;
          }
        endwhile;
        ?>

The results are paginated:

        echo paginate_links( array(
            'base' => str_replace( $big, '%#%', esc_url( get_pagenum_link( $big ) ) ),
            'format' => '?paged=%#%',
            'current' => max( 1, get_query_var('paged') ),
'total' => $fq->max_num_pages
        ) );

This works well in most cases:

• https://cdma.happy-dev.fr/?taxonomy=toute-formation&s=design
• https://cdma.happy-dev.fr/page/2/?taxonomy=toute-formation&s=design
• https://cdma.happy-dev.fr/page/3/?taxonomy=toute-formation&s=design

It fails in others:

• https://cdma.happy-dev.fr/?taxonomy=toute-formation&s=sophie
• https://cdma.happy-dev.fr/page/2/?taxonomy=toute-formation&s=sophie
• https://cdma.happy-dev.fr/page/3/?taxonomy=toute-formation&s=sophie

I ended up understanding that pagination of my formations was not working when I didn’t have enough actualites. That is, say I have a query that brings 10 formations, and 20 actualites: everything works as expected. The opposite fails however.

This is how I rewrite URLs regarding actualites:

function custom_rewrite_rules( $wp_rewrite ) {
  $wp_rewrite->rules = array(
    'actualite/page/?([0-9]{1,})/?$' => $wp_rewrite->index . '?pagename=actualite&paged=' . $wp_rewrite->preg_index( 1 ),

  ) + $wp_rewrite->rules;
}
add_action( 'generate_rewrite_rules', 'custom_rewrite_rules' );

I tried to had a prefix to the search URL thinking that could play a role, but to no avail.
I also tried adding a custom rewrite rule for the search page, but it is not having any impact. I still get 404s.
I spent hours digging every possible direction but to no avail.

Any suggestion is most welcome.
I don’t see why both pagination of formations and actualites are related.