$str = mb_convert_encoding($str, 'EUC-JP');
$encoded_str = rawurlencode($str);
ついでに
文字列の文字コードを判定
echo mb_detect_encoding($str);
とか
echo mb_detect_encoding($str, array('ASCII', 'UTF-8', 'EUC-JP'));
など。
第二引数のデフォルトはmb_detect_order()で、
手元ではASCIIとUTF-8しか含まれていなくて、EUC-JPが判定できなかった。