Now that you have access to the Western Sea, there are a few things you should do before going to Shaman Village (which is your next destination).
Core, the Mars Djinni
Core is in a forest accessed by the northwestern beach of Atteka (that's the southern continent in this ocean - Hesperia is the northern one). Keep going east from these beaches across a long forest and piece of land until you reach the end. Wander around in this forest until Core shows up. Defeat it in battle and it'll join you. Make sure you set it to Jenna.
Go back to your boat and go north from where you found Core to a beach on the southwestern side of Hesperia. Within view is a small settlement which you should enter. Climb up to the left and use Growth (you know what you need to do - reconfigure djinni) on the vine, and climb up. Move the box in the fenced-off area out the left-hand gap in the fence, then go down and push it into the enclosure. Go down again and Move it one to the right. Now you can get another Mars Djinni, Tinder, who joins without a fight, and 166 coins from the chest in the cave. Now, leave Hesperia Settlement.
Petra, the Venus Djinni
For an extra Venus Djinni, take the eastern river leading up through Hesperia (come in from the sea in between the two beaches). Not the western one, since that leads to Shaman Village, which is where you'll be going in a moment. Follow the river all the way until you reach a fork. The bottom route goes nowhere, and there's a small mountain to your north, so get off just past the mountain. Just to the north in this forest, wander around to find Petra. Defeat it in a random battle, and it'll join your party.
To Shaman Village
Get back on your boat and sail back to the sea. Go west and up the western river leading up from the south of Hesperia - you'll reach a very big lake. Take the right-hand river at the fork. Get off and enter the cave.
You can't do anything here for the mean time. The forward and right paths go nowhere, so take the left one (blow away the ivy with Whirlwind). Ignore the Mercury Djinni in here and just go around the top of the room and down to the door. Shove the pillar off into its slot and leave the cave via the exit to the right. Back on the world map, go east and enter Shaman Village.