Не вижу проблемы, нужен только небольшой рефакторинг.
По-хорошему, ajax должен запрашивать только данные, а не готовый html.
Ответ в результате ajax-запроса будет выглядеть примерно так:

{
    num_pages: 5,    // подсчитанное кол-во страниц, с учетом фильтров и т.п.
    page_limit: 50,  // кол-во записей на страницу
    data: [          // данные для текущей страницы
        { id: 123, text: "абырвалг..."},
        { id: 456, text: "абырвалг..."},
        { id: 789, text: "абырвалг..."}
    ]
}

сам запрос будет что-то типа такого:

$.ajax({
    url: "/data.php",
    method: "post",
    dataType: "json", // важно указать, что данные возвращаются в формате json. как вариант, можно прописать нужный header в ответе от PHP
    data: {
        param1: "фильтр 1",
        param2: "фильтр 2"
    },
    success: function(response) {
        // console.log(response); // для отладки
        if (response.data) {
            // тут код для заполнения и отображения таблицы
        }
        if (response.num_pages > 1) {
            // тут код для отрисовки пагинатора
            // для этого достаточно знать, сколько всего страниц будет и сколько записей на каждую страницу
        }
        // если страница одна, то можно не выводить пагинатор
    }
});

Далее, с помощью js на стороне клиента можно сформировать и таблицу, и пагинатор (см. комменты в коде выше).

Для пагинации можно взять любой готовый плагин jQuery, например, нашел вот такой простой плагин:
https://www.jqueryscript.net/other/simple-versatile-paginati...