deberias hacerlo con javascript, habrias q cambiar esto
} else {
echo "<a href='javascript
:paginacion($i)'>$i</a> ";
}
y crear una funcion js
function paginacion(pag){
location.href='?pagina='+pag+'&opt1='+getElementBy Id('opt1').value;
}
donde opt1 seria un combo o lo/s q quieras utilizar
despues obviamente los valores de los combos o el de paginacion deberias rescatarlos con el arreglo $_GET['opcion'];