The overall style is great! I love how the name of the sea fits into the "waves" texture.
But something needs to be done with the forests. The sea isn't blue, so why are the forests green? Plus their borders are way too exact. Right now I like the version without the forests more.
The border is great! If you decide to leave the squares empty, they could be reduced in size a little bit - but right now they are asking for something to be put inside, IMHO. Maybe some simple signs like runes or geometric figures?