Problem with pagination_links

Hello again,

i use in my Plugin-Backend some Custom Tables and i want to paginate them with paginate_links.
Now i have three “little” Problems. Under my table exist the Paginationlinks but…
1.) If click on Page 2 it shows me the Datasets correctly, but i cant go back to Page 1.
Page 1 is not marked as a link!!!
2.) If i am on Page 3 and click on “Next” it goes to Page 2. The same if i am on Page 6 e.g.
3.) The Paginationlinks are 123..6 Next. If i am on Page 3 i dont see 4 or 5

Here is my (terrible) Code

function mitarbeiter_loeschen() {
	global $wpdb;
	$table_lagerma = $wpdb->prefix . "za_lagerma";
	// Wurde das Formular abgeschickt dann entsprechend löschen
	if (isset ( $_REQUEST ["do"] ) && $_REQUEST ["do"] == "loeschen") {
		$loeschma = $_POST ['maid'];

		foreach ( $loeschma as $loeschid ) {
			$wpdb->query ( $wpdb->prepare ( "DELETE from $table_lagerma where id = %d", $loeschid ) );
		}
	}
	echo '<p><div class="wrap">';
	echo '<h2>Mitarbeiter loeschen!!!</h2>';
	echo 'Hier werden Mitarbeiter geloescht</p>';
	echo '<hr>';

	$per_page = 6;
	$paged = (get_query_var('paged')) ? get_query_var('paged') : 1;
	$page = intval ( $_GET ['paged'] );
	$total_pages = ceil ( $wpdb->get_var ( "SELECT COUNT(*) FROM $table_lagerma" ) / $per_page );
	$sql = $wpdb->prepare ( "SELECT * FROM $table_lagerma ORDER BY nname ASC LIMIT %d, %d", max ( $page - 1, 0 ) * $per_page, $per_page );
	$mitarbeiter = $wpdb->get_results ( $sql );
	echo '<form name="mitarbeiter_loeschen" method="post" action="">';
	echo '<h4> Angelegte Mitarbeiter<h4>';
	echo '<table><tr><td></td><td>Vorname</td><td>Nachname</td><td>Logistik</td></tr>';
	foreach ( $mitarbeiter as $ma ) {
		echo '<tr><td><input type="checkbox" name="maid[]" value="' . $ma->id . '"></td>';
		echo '<td>' . $ma->vname . '</td>';
		echo '<td>' . $ma->nname . '</td>';
		echo '<td>' . $ma->logistik . '</td></tr>';
	}
	echo '</table><input type="submit" id="buttonloeschen" value="Loeschen" onclick="return confirm(\'Wirklich loeschen?\');" />';
	echo '<input name="do" type="hidden" id="check" value="loeschen"></form></div></p>';
	$big = 999999999; // dummy
	echo '<p>';
	$paginate_links = paginate_links ( array (
			'base' => @add_query_arg('paged','%#%'),
			'format' => '?paged=%#%',
			//'current' => max( 1, $paged),
			'current' => max( 1, get_query_var('paged') ),
			'total' => $total_pages
	) );
	echo $paginate_links;

	echo '</p>';
}