過去に、さくらにインストールしました。
バージョンなども全く同じかと思います。

1..htaccess の削除

2.さくらコントロールパネルよりphp.iniへ設定

mbstring.language Japanese
output_handler mb_output_handler
mbstring.encoding_translation 1
magic_quotes_gpc=off
#php_flag session.use_cookies 0
#php_flag session.use_trans_sid 1
mbstring.http_output = UTF-8
mbstring.internal_encoding UTF-8
upload_max_filesize 5M

3.DBの 照合順序 を utf8_general_ci に変更

4.EC-CUBEでDBの値を取得している箇所の文字化けを解消
/data/class/SC_DbConn.php
56行目付近 変更
if(!isset($objDbConn->connection) || $new) {
if($dsn != "") {
$objDbConn = DB::connect($dsn, $options);
$this->dsn = $dsn;

/----kokokara
$buf = $objDbConn->prepare('SET NAMES utf8');
$objDbConn->execute($buf);
/----kokomade

5.商品名など検索が機能しない（管理画面含む）
/data/class/SC_DbConn.php
56行目付近 変更
$buf = $objDbConn->prepare('SET NAMES utf8');
$objDbConn->execute($buf);

/----kokokara
mysql_set_charset("utf8");
/----kokomade



この5項目で、動作しています。
参考になさって下さい。