Creo que el problema esta en tus links, intenta esto
Código PHP:
for( $i=1; $i<=$totalPag ; $i++)
{
$links[] = "<a href=\"paginaactual.php?pag=$i&pueblo=".$_GET['localidad']." \">$i</a>";
}
cambia donde dice "paginaactual" por la pagina donde estas relizando la paginacion, creo que estas perdiendo la vinculacion alli, por eso al cambiar no imprime "nada"