Creating search form for custom database table

I have a custom table in the WP database which I can display fine, with pagination, using the following code:

<?php

global $wpdb;
$rows_per_page = 50;
$current = (intval(get_query_var('paged'))) ? intval(get_query_var('paged')) : 1;

$rows = $wpdb->get_results( "SELECT * FROM nc_rates_eng"); 
global $wp_rewrite;

$pagination_args = array(
'base' => @add_query_arg('paged','%#%'),
'format' => '',
'total' => ceil(sizeof($rows)/$rows_per_page),
'current' => $current,
'show_all' => false,
'type' => 'plain',
);

if( $wp_rewrite->using_permalinks() )
$pagination_args['base'] = user_trailingslashit( trailingslashit( remove_query_arg('s',get_pagenum_link(1) ) ) . 'page/%#%/', 'paged');

if( !empty($wp_query->query_vars['s']) )
$pagination_args['add_args'] = array('s'=>get_query_var('s'));

echo paginate_links($pagination_args);

$start = ($current - 1) * $rows_per_page;
$end = $start + $rows_per_page;
$end = (sizeof($rows) < $end) ? sizeof($rows) : $end;

echo "<table width='100%' align='center' border='3px solid grey'>";
echo "<tr>";
echo "<th style='background: #B9C9FE;'>Destination</th>";
echo "<th style='background: #B9C9FE;'>Dial Prefix</th>";
echo "<th style='background: #B9C9FE;'>Cost per Minute (euros)</th>";
echo "</tr>";
echo "<tbody>";


for ($i=$start;$i < $end ;++$i ) {
$row = $rows[$i];

echo "<tr>";
echo "<td>$row->r_dest</td>";
echo "<td>$row->r_prefix</td>";
echo "<td>$row->r_rate</td>";
echo "</tr>";
}
echo "</tbody>";
echo "</table>"; 

echo paginate_links($pagination_args);

?>

However, I would also like to be able to take input from the user to search this table and display the results in the same format. What’s the best way to do this?

I tried adding a simple form to the top of the page and plugging the result into the sql query:

<form method="get" id="searchform" action="">
<p>
<label>Destination:</label> <input type="text" name="destination" id="destination" value="" />
</p>
<input type="submit" id="searchsubmit" value="GO" />
</form>

…..

$dest=$_GET['destination'];
$rates_sql="SELECT * FROM nc_rates_eng WHERE r_dest LIKE " ."'%$dest%'";

….

And this works, but breaks the pagination function.

Any help would be greatly appreciated!