Cualquier librería de paginación te debe de permitir trabajar con ajax.
Te dejo dos proyectos que te pueden servir:
https://github.com/whiteoctober/Pagerfanta https://github.com/Kilte/pagination
El tema no es nuevo en el foro así que procura hacer una búsqueda sobre el tema para mas información.