SJISならこれでいいんでは?
$str =~ s/([\x81-\x9f\xe0-\xfc])([\x40-\x7e\x80-\xfc])/sprintf("%%%02X%%%02X",ord($1),ord($2))/eg;

っと、半角カナ用にもう一押し必要か。残念!
\xa0-\xdf斬り。