Non è difficile.
L'ultima pagina la ricavi con la funzione CEIL, suppongo!
Tu sai qual'è la pagina corrente (prelevata via $_GET) e quella finale.


Codice PHP:
$pag = $_GET['pag']; 
$prev = $pag - 1; 
$succ = $pag + 1;
$ini = 1;
$ini2 = 2;
$center_left1 = $pag - 1;
$center_left2 = $center_left1 - 1;
$center_right1 = $pag + 1;
$center_right2 = $center_right1 + 1;

$end = xxx; // questo lo calcoli suppongo con il CEIL applicato
// al numero di risultati diviso il numero di righi per pagina 
$end2 = $end - 1;

$menu = "
<a href =\\"pagina.php?pag=$prev\\">Precedente</a>
<a href =\\"pagina.php?pag=$ini\\">$ini</a>
<a href =\\"pagina.php?pag=$ini2\\">$ini2</a>
 [....] 
<a href =\\"pagina.php?pag=$center_left2\\">$center_left2</a>
<a href =\\"pagina.php?pag=$center_left1\\">$center_left1</a>
 $pag 
<a href =\\"pagina.php?pag=$center_right1\\">$center_right1</a>
<a href =\\"pagina.php?pag=$center_right2\\">$center_right2</a>
 [....] 
<a href =\\"pagina.php?pag=$end2\\">$end2</a>
<a href =\\"pagina.php?pag=$end\\">$end</a>
<a href =\\"pagina.php?pag=$succ\\">Successivo</a>
"; 
Naturalmente puoi automatizzare la procedura in una funzione o simili, ma questo è (a mio avviso) un buon esempio di script.