初めまして。ストーリーが作れないとのことですが、「その話はどの位置にあるのか」という視点で考えてみてはいかがでしょうか？

・その話だけで完結する読切型
・次の展開に繋がる連載型
上記のどちらかによって、ストーリーの構成も決まってくると思います。

「読切型」である場合、起こる問題も小さい方が起承転結にまとめやすいと思います。他の方が言っていたような「皇帝と皇后の夫婦喧嘩」といった話とかですね。

「連載型」である場合、伏線を仕込みやすいです。大きな問題が起こってその場は解決するも「犯人は誰なんだ、何のためにやったんだ」と次の展開に繋げられます。

また「主人公たちの立場が高位すぎて大きな問題が起こせない」とのことですが、だからこそ悪役は「自分の手を汚さない方法」を考えると思います。

寿国の皇位継承がどうなっているのか分かりませんが、恐らく複数の時期皇帝候補がいるかと思われます。序列第十数位とかであればそんな気もないでしょうが、２、３位辺りは虎視眈々と皇帝の座を狙うのではないでしょうか。
鉄道の旅であることも、事故に見せかければ皇帝だけでなく皇后や腹心たちをまとめて葬れます。
暗殺者を雇う、兵や民の中に紛れ込ませる、魔法で鉄道のブレーキを効かなくさせて脱線させる、色々とできるのではと思います。

ドロドロした展開が嫌であれば、立ち寄った町の問題を解決する展開もあります。
例えば、視察に訪れた町は一見発展しているけど裏では貧富の差が激しくて、死罪を覚悟で貧民が直談判しにくる。それを主人公たちが滞在している間に官吏の汚職を暴くといった感じですかね。

長々と差し出がましいことを書き連ねてしまい、申し訳ありません。あくまでも「私だったらこうする」というものですので、相談の回答になっていなければ無視して下さい。
あなたの創作の一助になれたなら幸いです。