These are rather different things. The references to creation and the literal formation of Hyrule is referred to in ancient times; the land, creatures etc. had been formed by the Goddesses at creation, which is currently an undetermined amount of time before OoT, likely at least a thousand years.
What the Deku Sprout is referring to is political unification; before Link's birth, there had been a civil war in Hyrule because of conflict between the various groups and territories that form Hyrule, including the monarchy. This was happening around the time of Link's birth, and ended shortly after. From what we gather, by the beginning of OoT, all the states had unified under the monarchy with the exception of the Gerudo. Even though each society has their own respective leaders (and occasionally their own monarchies), they still have an allegiance to the Hylian Monarchy, likely as terms of agreement for ending the war; this is demonstrated by why so much of the game is influenced by Zelda's Lullaby, the melody of the Royal Family, because all the groups of Hyrule swore allegiance to the monarchy under unification, with the exception of the Gerudo. A neat little supplemental bit of evidence to this is the fact that you don't play Zelda's Lullaby at all (as far as I can recall) in the entire Gerudo Valley or Spirit Temple Segments in the game. This means that the Gerudo had not sworn allegiance to the royal family. At the beginning of OoT, Ganondorf is seen coming to Hyrule Castle to meet with the King to discuss a treaty of some kind; Ganondorf is proposing a peace treaty and/or offering to join the united Hyrule, which is a ploy to lull Hyrule into a sense of complacency so that they will not suspect attack from Ganondorf. This allows Ganondorf to carry through his plan and attack without suspicion.
