事前に頼んだほうが良いでしょう

ハワイなので日本人慣れしていて、日本人的感情を理解してくれたり
しますが、現地で頼んでもすでに満室のこともあるし、聞き入れてくれ
ないことも考えられます。

差額を払っても良いのであれば、予め文章で伝えておくべきでしょう。
「○○の事情でアップグレードをしてもらいたいのですが、
もし部屋に空きがあったらお願いできませんか。差額を払うのは
構いません。」とでも

しかし、
>そこで、ホテルは部屋を指定しないプランなのですが
という文章から察するに、パッケージか何かで泊まるのでしょうか?
所謂、Run-of-Houseですよね。パッケージならは、旅行代理店から
頼んでもらったほうが良いと思います。それでも誕生日程度では
どうでしょうか。新婚旅行ならアップグレードの確率は高まります
が、「たかが誕生日」として無視されるのではないでしょうか?
結婚記念日とかなら、まだ良いのでしょうが。

ハワイのようなリゾートでは海が見られる(この中にも細かいカテゴ
リーがありますが)か否かで料金が随分変わってしまいます。
個人手配ならば、予めそのカテゴリーにすべきで、また個人手配の
良さは、このような場合に希望が叶い易いということもあります。

その場で言う英語に関してですが、「模範解答」は出せますが、相手
から返ってきた言葉に対応できませんよね。そうするといくらしっかり
した英語でもそこでおしまい。想定外の英語がめろめろならば、従業員
も嫌がって相手にしてくれません。特に日本人団体客は日本語がダメと
思い込んでいるスタッフは逃げてしまいます。やはり事前に文章で頼ん
でおくべきだと思います。例文ですが、anが必要ですよ。