Your continent seems to have few islands to it, or must be separated by vast distances from the rest of the world. This indicates little need for searching other lands, through navy or otherwise. Or is it only some common belief, that there is no land outside this one? Well, I don't know your world. But let's have some ideas!
Exploring and Finding
(how to get the heroes there?)
- A hurricane carries a ship far away from its usual route. According to maps, there should be no land (or the edge of the world...), but there is an island, or more of them! When the ship returns, it spreads rumours about the discovery.
- Same as above, the heroes themselves are on board. They may want to explore now or later, or can be hired, or provoked on a mission if they spread the rumours.
- A magical experiment (Teleport or not) goes awry and transports them right onto that other continent!
- Diplomats from the other end of world arrive, offer peace and business. Whether they are so peaceful or not, local rulers will pay much for information about those lands.
- Old legends, a seer, or their finds indicate a land beyond the known maps. Don't forget to make them seem strange and exotic, no one would go to Old Boredomville!
- A person from that continent ends somehow up here. It wants home.
(and once they are there?)
Gods? That depends very deeply on your world.
A) The pantheon is basically the same. People worship the same gods, but maybe under different names, with slightly different agendas/portfolios. Your clerics keep their powers, but will have many discussions with other clerics of the "same" god. But, for various reasons, there may be "new" gods, or a god you worship is unknown here! Maybe the gods don't like it somewhere, have some agreement, or their worshippers were all killed in some holy war, or anything.
B) The pantheon is deeply different. Maybe it IS the same, just reversed? (Try to somehow invert all your deities. A Good deity could be made into an Evil deity but similar, etc.)
Or entirely new deities. Maybe the world's size does not allow them to spread their holy powers across both continents. Your clerics may be powerless. The gods have probably an agreement about not crossing their ways. In the long run, this may be hard for the heroes, if gods themselves want no mixing between both continents.
B2) Similar as above, but the gods have no agreement or even don't know of that Other Side! To be honest, this means sooner or later a Holy War, or several. I would not use this option.
C) Do something different. You have that usual gods on your continent? People may worship in other ways. The Spirits of all kinds, from shamanism to voodoo. Strange holy beings and demons. Great heroes of the past. Celestial bodies. A pantheon with thousands of gods and beings. The Four Winds...
A new race or few may do good. Or at least a subrace of a known race.
I think there should not be TRULY new classes. Now for all the exceptions:
- Different gods give different powers. Different ways of worshipping too.
- Maybe the magic works somewhat differently, means different uses for it.
- Technology and research make new classes possible, as do materials and sources unknown elsewhere. Best seen on magic-users: magic based on strange crystals, wild magic, Blood magic, elemental magic, Sand magic, Song magic...
- Classes you seemed to know? Twist them! Druids are usually close to nature anywhere. On this continent, their power is in deep woods only. Make rangers followers of a particular deity, or not if they are.
Some of the new classes may be easily adapted on the old continent, some not.