Tanto como lo del 1 2 3 4 5 no se, mejor dicho se podría pero creo que habría que crear un bucle con while o algo así, lo otro es tocar esta zona del código...
//desplazamiento
echo "<a onclick="Pagina('1')">Primero</a> ";
if($PagAct>1) echo "<a onclick="Pagina('$PagAnt')">Anterior</a> ";
echo "<strong>Pagina ".$PagAct."/".$PagUlt."</strong>";
if($PagAct<$PagUlt) echo " <a onclick="Pagina('$PagSig')">Siguiente</a> ";
echo "<a onclick="Pagina('$PagUlt')">Ultimo</a>";
Quizás estaría lindo cambiar el Primero por un « («) el Ultimo por un » (»)
Y poner <strong>Página ".$PagAct." de ".$PagUlt."</strong>