Would it be possible to change my seat to another one?
If it is not too much trouble, could you change my seat?
Could I change my seat?
「丁寧に 」というご希望でしたので、できるだけ丁寧な表現をご紹介致しました。
Would it be possible to ~
と言うのは、「~することは可能でしょうか」というかなり丁寧な言い方です。
（これのやや丁寧度が下がる言い方は、Is it possible to~? です。これはそれほどフォーマルでもなく、またカジュアルでもない、中間の言い方です）
また、2つめの例文のように、
If it is not too much trouble, could you~?
というのもかなり丁寧な表現になっています。
（もしご面倒でなければ、~して頂けますか？）
ですが、そこまで丁寧に言う必要もない場合は、3番目のように
Could you~?
（～していただけますか？）
といいます。
これは、大変よく使われる文で、Can you~?に比べると、丁寧な感じの文になります。
なお、『席を替わる」は
change one's seat
あるいは、
change one's seat to another one
といいます。
もう一つの提案として、
空いている席（移動したい場所）を指さして、
~~~~~~~~~~~~
Can we move there?
Mind if we move there?
Would it possible to move there?
~~~~~~~~~~~~
のどれかを言うと、
後から「Where would you like to move?」（「ご希望の席はありますか？」）
などの質問はなく、
相手の店員さんはどこに移動したいかが分かるため、
話が一段階早くなります。
例：
~~~~~~~~~~~~
A:
Waitress, excuse me, but mind if we move there?
（あ、ウェトレスさん。そこに移動してしまっても大丈夫ですか？）
B:
Sure, I'll get you set up.
（畏まりました。お皿など持っていきますね。）
~~~~~~~~~~~~
日本 
アメリカ合衆国 
