As I recall, It wasn't a birthmark. The entire crest itself appeared on his birthday. This might be JP/US fumbling though. After all, the Oracle games were supposed to be a remake once, and Ages begins with a pre-crested Link saving Impa from monsters.
As for a lot of the debate on Link's prior experience, I think much of it can be summed up as likely being similar to Miyamoto's intentions for the player. Although Link does not literally grow into an adult over the course of the game, Miyamoto has been quoted regarding Zelda 1 as saying that the player essentially starts off as a child, and matures as they gather more fragments. It is very likely that Link had no idea what he was doing, but figured it out as he went along and became both skilled and deadly by the time he slew Ganon. There's several anime and manga out there about boys Link's age who follow this path, and if they keep at it, you do see some impressive development.
As for Link coming from another province... it seems a strange thing to say Link came from elsewhere if that's all it means. Also, the context of Zelda II seems to imply that when Link "decided to stay in Hyrule", he wasn't referring to the overworld of the first game. Even though it says he was helping to rebuild, you still don't see any structures in Death Mountain Area.