Given you've got incredibly strong creatures who make the heavy lifting/reaching high places easy, PLUS an incredibly strong base of support for very popular leaders (Cair Paravel, so I'm assuming we're talking the Pevensies, who circa Prince Caspian, as I recall, were figures of nearly religious proportions, so if your demi-gods come down and need a place to live you're going to get to work building them one right quick), I'm thinking it could get done pretty quickly -- five years at most seems reasonable, given the relatively ideal circumstances for them. If nothing else, if you need it done in a relatively short timespan, you can handwave it as fantasy.

Actually, the construction itself could be a pretty hilarious subplot.