WordPress Pagination not working Properly with Custom Post Type

Question

I have a WordPress Project. I have page template where I retrieve post type "company". I also have pagination.

Pagination is set up to work in a following way (url): https://example.com/companies/?paged=2

but instead, it's redirecting to following url: https://example.com/companies/page/2/

As a result, I get 404 error on both urls.

Although, when I hover the url, it shows https://example.com/companies/?paged=2

Below is the main parts of the code. What can be causing this issue? I would appreciate your help.

<?php // Template name: Page - Companies

get_header();

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

$search_query = isset($_GET['search']) ? sanitize_text_field($_GET['search']) : '';

$args = new WP_Query(
    array(
        'post_type'      => 'company',
        'post_status'    => 'publish',
        'posts_per_page' => 10,
        'paged'          => $paged,
        'meta_key'       => 'display_order',
        'orderby'        => 'meta_value_num',
        'order'          => 'DESC',
        's'              => $search_query
    )
);
?>

<?php if ( $args->have_posts() ) : ?>
    <div class="grid gap-[30px] xl:gap-[35px_80px] xl:grid-cols-2">
        <?php while ( $args->have_posts() ) : $args->the_post();
            $logo = get_field('logo');
            $rating = get_field('rating') ?? '0.00';
            $address = get_field('address');
            $found_date = get_field('found_date');
            $working_days = get_field('working_days');

            $reviews = get_field('reviews');
            $reviews_count = 0;
            if ($reviews) $reviews_count = count($reviews);

            $avatar = '';
            $branch_slug = get_field('slug');
            $api_url = BACKEND_URL . '/api/frontend/branches/' . $branch_slug;
            $response = wp_remote_get($api_url);
            $branch_data = json_decode(wp_remote_retrieve_body($response), true);
            $avatar = $branch_data['data']['avatar'];
        ?>
            <!-- My HTML here... -->
        <?php endwhile; ?>
    </div>

    <div class="flex items-center justify-center gap-[10px] [&_.page-numbers]:flex [&_.page-numbers]:w-[40px] [&_.page-numbers]:h-[40px] [&_.page-numbers]:items-center [&_.page-numbers]:justify-center [&_.page-numbers]:text-center [&_.page-numbers]:text-[14px] [&_.page-numbers]:rounded-[8px] [&_.page-numbers]:bg-light [&_.page-numbers]:transition-colors [&_a.page-numbers:hover]:bg-secondary [&_a.page-numbers:hover]:text-white [&_.icon]:w-[10px] [&_.page-numbers.current]:bg-primary [&_.page-numbers.current]:text-white [&_.page-numbers.current]:text-white mt-[50px]">
        <?php
        echo paginate_links( array(
            'total'        => $args->max_num_pages,
            'current'      => max(1, get_query_var('paged')),
            'format'       => '?paged=%#%',
            'show_all'     => false,
            'end_size'     => 1,
            'mid_size'     => 1,
            'prev_next'    => true,
            'prev_text'    => __('<i class="icon icon-chevron-left"></i>'),
            'next_text'    => __('<i class="icon icon-chevron-right"></i>'),
            'type'         => 'plain',
        ));
        ?>
    </div>

    <?php wp_reset_query(); ?>
<?php else: ?>
    <div class="text-[#0c3659] font-medium text-[18px] text-center mt-[50px]">No results were found for your search query. Please try again.</div>
<?php endif; ?>