I think I figured it out. It could be done using a Zaratan and a teleportation spell.
- The castle and the village exist on the back of an ancient Zaratan.
This wiki (Which cites the Arms and Equipment Guide 3rd edition) talks about Zaratans' being capable of supporting small villages.
Older zaratani were comfortable supporting small villages so long as the inhabitants did not disturb their slumber. A few corsairs even used them as hidden bases. The most famous of these was Jayani al-Jasir.
Many inhabitants of zaratan islands were incredibly superstitious. They believed that their island was a deity whose wrath would be terrible if disturbed. Large quantities of fish, and even visitors, were sacrificed to please the zaratan.
The only 5e source I've found doesn't explicitly state that you can live on a Zaratan, but it does support that they are gargantuan and that their shells are capable of supporting a "landscape":
When a zaratan is summoned from the Elemental Plane
of Earth, the ground rises up to take the shape of what
looks like a hulking, armored reptile, its shell composed
of the landscape from which it arose.
Gargantuan elemental, neutral
(Page 201, Mordenkainen’s Tome of Foes)
The lake is artificial, is a dip in the zaratan's shell, or is just not part of the teleportation (perhaps there are similar lakes in both locations, perhaps the zaratan lives in one of two large lakes that it is sometimes teleported between)
As long as the Zaratan is alive and willing, the Teleport spell can be used to teleport it, the village and castle (which are part of it's shell), and up to 7 willing residents to the new location.
This spell instantly transports you and up to eight willing creatures of your choice that you can see within range, or a single object that you can see within range, to a destination you select. If you target an object, it must be able to fit entirely inside a 10-foot cube, and it can't be held or carried by an unwilling creature. The destination you choose must be known to you, and it must be on the same plane of existence as you.
- The zaratan would be too large to use Teleportation Circle, and any attempts to shrink or polymorph it could be devastating to the residents or even the zaratan itself
- If the zaratan dies, it's body might be considered an object, causing the village to become un-teleportable (it would also be hard to justify it being a willing creature).