self-contained example that seems to work fine on my machine...
<?php
// added numeric code entity to reflect actual code of OP
// $param = 'Josef Kricenský';
$param = 'Josef Kricenský';
$param = html_entity_decode($param , ENT_XML1, 'UTF-8');
// this is not how you check for utf-8 encoding
// ...except  in this simple example ;-)
// all characters but the ý are encoded in one byte, ý uses two bytes 
// -> 16 bytes -> strlen($param) should be 16
if ( 16!=strlen($param) ) { 
    die("this doesn't seem to be utf-8 encoded");
}
// the mysql_ api is deprecated. Take a look at e.g. http://docs.php.net/pdo for alternatives
$mysql = mysql_connect('localhost', 'localonly', 'localonly') or die(mysql_error());
mysql_select_db('test', $mysql) or die(mysql_error($mysql));
// SET NAMES 'utf8' doesn't tell the client library about the changed encoded
// so e.g. mysql_real_escape_string() may fail
// see http://docs.php.net/mysql_set_charset
mysql_set_charset('utf8', $mysql) or die(mysql_error($mysql));
// using a temporary table for this example...
setup($mysql);
// insert a record
echo "insert a record\n";
$query = sprintf("INSERT INTO soFoo (name) VALUES ('%s')",
    mysql_real_escape_string($param, $mysql)
);
mysql_query($query, $mysql) or die(mysql_error($mysql));
// retrieve the record
echo "retrieve the record\n";
$result = mysql_query('SELECT name FROM soFoo', $mysql) or die(mysql_error($mysql));
while( false!==($row=mysql_fetch_assoc($result)) ) {
    echo 'strlen($row[name])==', strlen($row['name']), "\n";
}
function setup($mysql) {
    mysql_query('
        CREATE TEMPORARY TABLE soFoo(
            id int auto_increment,
            name varchar(32),
            primary key(id)
        ) DEFAULT CHARSET=utf8
    ', $mysql) or die(mysql_error($mysql));
}
prints
insert a record
retrieve the record
strlen($row[name])==16