貴重なご意見ありがとうございます。
若干検証してみましたが、自社サイトもUTF-8にて構築し、PaypalサイトへSubmitしたところ、問題なくデータを受け渡すことができました。ただ、実際にはDBやサーバーの設定でEUC-JPがメインのエンコードになっているため、結果的にはマルチバイトはサブミットしない形で対応することにしました。
Paypalに問い合わせたところ、日本語は
https://www.paypal.com/cgi-bin/webscr
ではなく
https://www.paypal.com/j1/cgi-bin/webscr
を使用する旨回答が来ましたが、どちらにせよUTF-8でないと正しくデータは受け渡せず、逆にj1の方に飛ばすと全て日本語になってしまうなど弊害もあり、少々不本意な形ではありますが、上記の対応で行くことにしました。