Вы должны конвертировать из SJIS в UTF-8, а затем кодировать URL, а не из UTF-8 в SJIS, верно?
Как вы сказали "кодировка сайта - Shift_JIS".
<?php
$var = "北海道**";
$new = mb_convert_encoding($var, "SJIS", "UTF-8");
echo urlencode($new); // outputs %96k%8AC%93%B9%2A%2A
?>