First of all, I get different results on your site then you've described: it shows k113.2.html where 2 - is the page number I was on, not 35.
Try replace in includes/sessions.php:
$url = str_replace('categories.php', 'cat'.$matches1[1].'.'.$matches2[1].'.htm', $url);
$query = str_replace('cat_id='.$matches1[1].'&', '', $query);
$query = str_replace('&cat_id='.$matches1[1], '', $query);
$query = str_replace('cat_id='.$matches1[1], '', $query);
$query = str_replace('page='.$matches2[1].'&', '', $query);
$query = str_replace('&page='.$matches2[1], '', $query);
$query = str_replace('page='.$matches2[1], '', $query);
With:
$cat_url = get_category_url($matches1[1]);
$url = str_replace('categories.php', 'cat'.$cat_url.'.htm', $url);
$query = str_replace('cat_id='.$matches1[1].'&', '', $query);
$query = str_replace('&cat_id='.$matches1[1], '', $query);
$query = str_replace('cat_id='.$matches1[1], '', $query);