Hola,
La consulta:
else {$sql= "SELECT * FROM Todas WHERE Grado LIKE '%{$criterio_txt'";}
no creo que este bien. Supongo que querias algo como la otra, algo asi:
else {$sql= "SELECT * FROM Todas WHERE Grado LIKE '%$criterio_txt%'";}
Imagino que habra sido los dedos locos
Y para lo de opcionbusca_txt, es simplemente añadir otro parametro en el link que generas. Es mas, ya le has puesto nombre, el criterio2 que lees con el GET. Seria:
echo "<a href='buscador.php?pagina=" . $i . "&criterio=" . $criterio_txt ."&criterio2=".$opcionbusca_txt."'>" . $i . "</a> ";
Igual que con el otro criterio de busqueda.
Resumiendo: debes ser capaz de leer las variables tanto del formulario (POST) como del link de la paginacion (GET); y debes pasar (propagar) por el link de la paginacion todos los valores que necesites (normalmente, los que recibes del formulario) para usarlos como datos en las distintas paginas.
Saludos.
PD: Aunque te funcione con el codigo que te he dado, vuelve a darle un repaso y asegurate que entiendes como funciona.