1) я поменял mysql_escape_string на mysql_real_escape_string, т.к. mysql_real_escape_string экранирует строку с учетом текущей кодировки. почитайте в документации про нее, чтобы я не копипастил).
2) Апостроф ` поменял на одинарную ковычку, апострофом я обычно экранирую поля, таблицы, а не строки, хотя не проверял экранированные строки с апострофом.
3) Конечно надо избавляться от mysql и заменить на такие же функции mysqli, хотя где то может поломаться.
4) Странная запись $fio = mysql_escape_string($fio);
это скорее register glogals включен, было бы правильнее, универсальный подход $fio = mysql_escape_string($_REQUEST['fio']);
но может данные пришли из $_GET или $_POST
5) И как вариант данные пришли в кодировке cp1251, поэтому ошибка 1300 : Invalid utf8 character string
$fio = mysql_real_escape_string( iconv('windows-1251', 'utf-8', $fio));
mysql_query("SET NAMES 'utf8'");
$fio = mysql_real_escape_string($fio);
$rank = mysql_real_escape_string($rank);
$razryad = mysql_real_escape_string($razryad);
$region = mysql_real_escape_string($region);
$query = "INSERT INTO users(name, level, rank, region) VALUES('$fio', '$razryad', '$rank', '$region')";
$result = mysql_query($query);