This has to be Suppose a Kid from the Last Dungeon Boonies Moved to a Starter Town.
From Baka-Updates:
Follow the story of Loyd, an oblivious boy from a village in the countryside, who wishes to become a soldier in the capital. After convincing the mayor of his village, a loli witch, who is over a 100 years old, he sets off to the capital to fulfill his dream!
I wasn't sure at first, because your initial description was a little off, but with the extra details you added in your last edit, there's just too much that matches for this not to be the same manga.
The protagonist is Lloyd Belladonna, and he's not from an island, but a remote village in a monster-infested region next to the last dungeon.
Also, the village isn't forgotten. It's actually quite famous because it's the home of legendary heroes and their descendants, but normal people don't venture into that region, because it's so dangerous. The residents of the village are only able to survive there because they're all abnormally strong, and taking down monsters is no big deal to them.
Anyway, at the start of the first chapter, Lloyd leaves his home of Konron Village and journeys to the capital of the Azami Kingdom -- both of which are located on the same continent -- where he hopes to sign up as a soldier. The mayor of his village, Alca, gave him a special crystal and told him to find the Witch of the East Side -- also known as Maria Azami, daughter of King Azami -- who'd take care of him, since she used to be Alca's student.
In the second chapter, Lloyd meets Celine Hermione -- also known as 'The Cursed Belt Princess' -- who, as a little girl, wrapped a belt she found among her father's collection of 'unusal items' around her head, and had been stuck with it ever since, because no one had found a way to remove it.
Soon after meeting and being touched by Lloyd though, she finally manages to remove belt, much to her relief. She then recalls an old man once telling her that a strong person's power could remove the curse, and subsequently becomes infatuated with Lloyd.
Note that I've used the spellings of the various names from the actual manga in this description. The website I've provided links to uses slightly different spellings, which appear to be derived from the anime.
