La pregunta es un tanto antigua y conviene actualizar, no solo para optimizar, también para facilitar el mantenimiento a futuro. Mis recomendaciones:

 1. Desde PHP envía solo datos en formato JSON, que te ayudará a reducir significativamente el contenido de cada petición y, por consiguiente, el tiempo de respuesta
 2. En Javascript recibes los datos y generas el HTML necesario para agregar filas a la tabla y para generar los enlaces de paginación
 3. Agrega tantos campos de filtro como sean necesarios e inclúyelos todos en las peticiones, no importa si están vacíos o no, eso ya se resolverá al crear la consulta en PHP
 4. Para evitar errores, la tabla debe existir desde que se carga la página y se va modificando al obtener datos; lo mismo para la lista donde van a aparecer los enlaces de paginación
 5. Asigna una misma función para todos los campos y enlaces de paginación, tienen que estar relacionados para poder tener la funcionalidad esperada
 6. En los enlaces para ver/modificar clientes, no uses ID, porque son numéricos y se duplican. En su lugar usa [atributo de datos](https://developer.mozilla.org/es/docs/Web/API/HTMLOrForeignElement/dataset): `data-id="id-de-cliente"`
 7. Las [plantillas de texto](https://developer.mozilla.org/es/docs/Web/JavaScript/Reference/Template_literals) son ideales para crear HTML de enlaces y filas de la tabla.

<!-- begin snippet: js hide: false console: true babel: false -->

<!-- language: lang-js -->

    // Página actual, se va a usar para peticiones y enlaces de paginación
    let curPage = 1;

    function loadAjax(page = 1) {
        // Incluir todas las opciones de filtro y paginación
        let params = {
            pagina: page,
            elementos: $('#elementos').val(),
            tipo: $('#tipo-cliente').val(),
            nombre: $('#nombre-cliente').val()
        };
        // Número de página actual, para crear enlaces
        curPage = page;
        $('.data-pagination').html('<li class="loading">Loading...</li>');
        $.ajax({
            type: "GET",
            // Misma página para todos los filtros
            url: 'paginacion.php',
            // Enviar parámetros
            data: params,
            // Recibir respuesta como JSON
            dataType: 'json',
            // Ejecutar en función aparte
            success: drawTable
        }).fail(function(xhr, status, message) {
            console.log(status, message);
            curPage = 1;
            $('.data-pagination').fadeOut('1000', function() {
                $(this).html('Error cargando datos');
            }).fadeIn('1000');
        });
    }

    function drawTable(data) {
        // Eliminar registros actuales en la tabla
        $('.tr-cliente').remove();
        
        let records = data.clientes.length;
        let pages = parseInt(data.pages) || 1;
        if(records == 0) {
            // No hay información para mostrar
            $('#empty').show();
            $('.data-pagination').html('');
        }
        $('#empty').hide();
        data.clientes.forEach(cliente => {
            $('#data-table tbody').append(
                `<tr class="tr-cliente">
                    <td>${cliente.idCliente}</td>
                    <td>${cliente.nomCliente}</td>
                    <td>${cliente.tipoCliente}</td>
                    <td>
                        <span class="view-data" data-id="${cliente.idCliente}">Ver</span>
                        <span class="edit-data" data-id="${cliente.idCliente}">Editar</span>
                    </td>
                </tr>`
            );
        });
        // Crear enlaces de paginación enviando total de páginas disponibles
        pagination(pages);
    }

    // Crear elemento de lista con enlace de página
    function getPageLink(page, text) {
        if(!text) {
            text = page;
        }
        return `<li><a href="#" data-page="${page}">${text}</a></li>`;
    }

    function pagination(pages) {
        // Eliminar posible contenido anterior
        $('.data-pagination').html('');
        // Crear enlace anterior solo si página actual no es la primera
        if(curPage > 1) {
            $('.data-pagination').append(getPageLink(curPage - 1, 'Anterior'));
        }
        // Crear enlaces para todas las páginas disponibles
        for(let i = 1; i <= pages; i++) {
            $('.data-pagination').append(getPageLink(i));
        }
        // Crear enlace siguiente solo si página actual no es la última
        if(curPage < pages) {
            $('.data-pagination').append(getPageLink(curPage + 1, 'Siguiente'));
        }
    }

    $(function() {
        // Escuchar cambios en campos de filtro, se pueden seleccionar todos en una misma línea
        $('#elementos, #tipo-cliente, #nombre-cliente').change(loadAjax);

        // Escuchar eventos para ver y editar, delegados a la tabla
        $('#data-table').on('click', '.view-data', function() {
            // Obtener ID
            let idCliente = $(this).data('id');
            console.log('Ver: ' + idCliente);
            // Aquí lo que necesites hacer para mostrar más información
        });
        $('#data-table').on('click', '.edit-data', function() {
            // Obtener ID
            let idCliente = $(this).data('id');
            console.log('Editar: ' + idCliente);
            // Aquí lo que necesites hacer para editar
        });

        // Escuchar eventos en enlaces de paginación, delegados a UL
        $('.data-pagination').on('click', 'li a', function(e) {
            e.preventDefault();
            let page = parseInt($(this).data('page')) || 1;
            console.log(page);
            loadAjax(page);
        });

        // Ejecutar con valores por defecto
        loadAjax();
    });


    /* *********** PROBANDO ********
     * Este es un ejemplo de la estrucutra que debes recibir desde PHP
     */
    let data = {
        // El total de páginas debe ser 1, pero...
        pages: 5, // ...solo para mostrar más enlaces y ver que funciona
        clientes: [
            { idCliente: 1, nomCliente: 'StackOverflow', tipoCliente: 'Normal' },
            { idCliente: 2, nomCliente: 'Apple', tipoCliente: 'Distribuidor' },
            { idCliente: 3, nomCliente: 'Google', tipoCliente: 'Mayorista' },
        ]
    };
    // 
    setTimeout(drawTable, 1500, data);
    /* ********** Fin de pruebas ********** */

<!-- language: lang-css -->

    #data-table {
        margin:20px auto;
    }
    .data-pagination {
        list-style:none;
        margin:20px 0;
        text-align:center;
    }
    .data-pagination li {
        display:inline-block;
        margin:0;
        padding:0 10px;
    }

<!-- language: lang-html -->

    <script src="https://cdnjs.cloudflare.com/ajax/libs/jquery/3.3.1/jquery.min.js"></script>

    <div>Elmentos por página:
        <select id="elementos" name="elementos">
            <option value="10" selected>10</option>
            <option value="25" >25</option>
            <option value="50" >50</option>
            <option value="100">100</option>
        </select>
    </div>
    <div>Filtrar por tipo:
        <select id="tipo-cliente" name="tipo-cliente">
            <option value="" selected>Todos</option>
            <option value="normal">Normal</option>
            <option value="distribuidor">Distribuidor</option>
            <option value="mayorista">Mayorista</option>
        </select>
    </div>
    <div>Buscar por nombre:
        <input type="text" id="nombre-cliente" name="nombre-cliente" value="">
    </div>

    <table id="data-table" class="table bootgrid-table">
    <thead>
        <tr>
            <th>ID</th>
            <th>CLIENTE</th>
            <th>TIPO</th>
            <th>ACCIÓN</th>
        </tr>
    </thead>
    <tbody>
        <tr>
            <td colspan="4" id="empty">No hay información para mostrar</td>
        </tr>
    </tbody>
    </table>
    <ul class="data-pagination"></ul>

<!-- end snippet -->

En PHP vas a recibir en `$_GET` lo siguiente: pagina, elementos, tipo y nombre. Y debes validar cada uno para saber si se deben incluir en la consulta, de preferencia, con asignación ternaria; por ejemplo:

    // Si está en $_GET, debe ser entero, de lo contrario, se asigna 1
    $pagina = (!empty($_GET['pagina'])) ? (int) $_GET['pagina'] : 1;
    // Valor en $_GET o cadena vacía
    $nombre = (!empty($_GET['nombre'])) ? $_GET['nombre'] : '';

Ya teniendo todas las variables, debes analizar cada una para saber si es necesario agregarla a filtros y vas a necesitar ejecutar dos consultas, una para contar las filas y otra para obtenerlas. Revisa los comentarios en el código para saber qué hace cada cosa.

    <?php
    // Obtener todos los parámetros necesarios
    $pagina = (!empty($_GET['pagina'])) ? (int) $_GET['pagina'] : 1;
    $elementos = (!empty($_GET['elementos'])) ? (int) $_GET['elementos'] : 1;
    $tipo = (!empty($_GET['tipo'])) ? $_GET['tipo'] : '';
    $nombre = (!empty($_GET['nombre'])) ? $_GET['nombre'] : '';
    
    // Crear un arreglo para filtros, tipo de parámetros y valores de remplazo
    $filtros = [];
    $tipos = '';
    $valores = [];
    
    // Verificar tipo para agregar a filtros
    if($tipo != '') {
        $tipos .= 's'; // Si es entero, cambia por 'i'
        $filtros[] = 'tipoCliente = ?';
        $valores[] = $tipo;
    }
    // Verificar nombre para agregar a filtros
    if($nombre != '') {
        $tipos .= 's';
        $filtros[] = 'nombre LIKE ?';
        $valores[] = "%$nombre%";
    }
    
    // Crear cadena de filtro, solo si se seleccionó una o más opciones
    $filtro = (count($filtros) > 0) ? 'WHERE ' . implode(' AND ', $filtros) : '';
    
    // Crear el arreglo a devolver como JSON
    $data = [
        'pages' => 1,    // Total de páginas disponibles
        'clientes' => []   // Clientes encontrados
    ];
    
    // Contar total de filas encontradas
    $smCuenta = $con->prepare("SELECT COUNT(*) as total FROM cliente $filtro");
    // Agregar valores de filtros
    if(count($filtros) > 0) {
    	$smCuenta->bind_param($tipos, ...$valores);
    }
    $smCuenta->execute();
    $smCuenta->store_result();
    $smCuenta->bind_result($total);
    // Leer consulta
    $smCuenta->fetch();
    $smCuenta->close();
    
    // Solo si se encontaron filas
    if($total > 0) {
        // Actualizar total de páginas disponibles
        $data['pages'] = ceil($total / $elementos);
        // Calcular inicio de consulta
        $offset = ($pagina - 1) * $elementos;
        // Incluye todos los campos necesarios
        $consulta = "SELECT idCliente, nomCliente, tipoCliente FROM cliente $filtro LIMIT $offset, $elementos";
        $smCliente = $con->prepare($consulta);
        if(count($filtros) > 0) {
            $smCliente->bind_param($tipos, ...$valores);
        }
        $smCliente->execute();
        $smCliente->store_result();
        $smCliente->bind_result($idCliente, $nomCliente, $tipoCliente);
        // Recorrer resultados
        while($smCliente->fetch()) {
            // Insertar datos en arreglo
            $data['clientes'][] = [
                'idCliente' => $idCliente,
                'nomCliente' => $nomCliente,
                'tipoCliente' => $tipoCliente
            ];
        }
        $smCliente->close();
    }
    // Devolver arreglo con total de páginas y filas encontradas
    echo json_encode($data);

En este ejemplo solo se agregaron dos opciones para filtrar, pero fácilmente puedes agregar más:

 1. Crea el campo en HTML
 2. En Javascript escucha los cambios para llamar a la función `loadAjax()`
 3. En la función agrega el campo y su valor en los parámetros de la petición
 4. En PHP crea la variable correspondiente y analiza para agregar a las variables para filtros, tipos y valores
 5. Si requieres más columnas para la tabla:
   * Modifica la tabla HTML para agregar la columna
   * En Javascript modifica la función `drawTable()` para mostrar esa columna
   * En PHP modifica la consulta, junto con `->bind_result()` y agrega el dato en el arreglo