You wake up on the shores of a distant land, and a fisherman called Devon talks to you. You should get to know him, as he is a very important character. If you choose the right options or talk to him again, he will direct you to Bentic the scholar. When you tell him Goodbye, he will tell you that you can take his things and that there appears to be trouble on the docks.
Devon said you can take his things, so do so. The bedroll is very handy, so double click it to roll it and take it with you. You can also take Devon's food if you intend to eat during your travels.
Now, it's time to see what's going on at the Docks. Go west until you come to a wooden staircase, going up to the docks. There, you will find two barrels. One contains a box and a bottle, and the box holds a dagger and, if you have the patch, it will also have the keyring. Equip the dagger and take the keyring. The other barrel has a scroll about the Skull of Quakes, which you will encounter during your pilgrimage to the Zealan Shrine, and some mushrooms.
If you go north to the gates of Tenebrae, the guard will tell you that the gates are closed and will remain so until the execution takes place. So just go south and watch the execution, where Toran is decapitated by Shaana by Mordea's command. Toran's head falls into the sea and is eaten by a minion of the lurker, and then everyone leaves while Rhian sobs over her husband's body and Tarna turns to you. You can read what is said and what happens in the execution since I have it online. You have no choice but to answer Tarna's questions, then you are free to go.
This part is optional, but will get you some useful things. If you go onto the higher ground, on the east side of the docks, you will notice two things - a locked chest in a ruined wooden building and a patch of adventurers' mushrooms which you will recognise by their yellow colour and green spots. You should take some of these mushrooms with you, as they will heal you when you eat them. Do not confuse them with the poisonous mushrooms you will find on the west side of the docks (they have red spots), as those will deduct hit points instead.
Now let us open that chest... be warned, however, that it is trapped. Go back down onto the lower ground and follow the shore east, and keep following it when it turns north, until you come to the wall. There, behind a tree, is a box. It is very hard to spot as it is well camouflaged, but this picture will help you to locate it. It has the key to that chest as well as a couple of potions. Add the key to your keyring (if you have the keyring, which is only available in the patched version) and take the potions, and now you can go and open the chest, which will explode upon opening, but you can easily heal yourself. It is well worth it because you will find five death disks on the skeleton inside, and a helmet. Now, go to the Tenebrae gates, north of the docks. Answer the guard's questions and enter.
You are now in Central Tenebrae. To the north is the Tempest's Palace, and west and east are two other parts of Tenebrae. The poor folk live in the west while the richer people inhabit the east. If you are desperate for equipment, you will see two locked guard towers connected by a bridge to the north. You can climb onto the bridge and loot the place, but it is stealing, so don't get caught.
Now, go north to the palace. Go on the roof by either climbing from the door of the palace or by using a staircase inside. In the middle of the roof, you will see a Recall Pad - a grey square which will rise and start pulsating when you go near it. Go near it and activate it - it will save you lots of trouble later on. There is also a patch of adventurer's mushrooms just outside the east wing of the palace if need healing or want to stock up on it.
Now that the Recall Pad on the palace in Central Tenebrae is active, you can now get off the roof and go to East Tenebrae, where Bentic lives.
Your objective now is to speak to Bentic, the scholar and librarian. I at first had trouble locating the library - it is near the northwestern edge of East Tenebrae. Bentic should be upstairs, or else on the west part of the library downstairs. You will recognise him by his green shirt. Ask him about Tenebrae and about leaving Pagan, and tell him you wish to leave Pagan. Bentic will direct you to Mythran, so ask him where he lives. He will say you must go north of Tenebrae and enter a cave that leads to the Plateau, where Mythran lives. Go back to Central Tenebrae, then run through the palace and leave via the northern exit.
North of Tenebrae is the Herdsman's Valley, home to torax farmers. Following the path north will lead you to the cave you are looking for. There is usually a troll patrolling there, and it is best to evade it. Enter the cave.