This is largely conjecture, but the etymology of this phrase is most likely related to the phrase "tuck in", meaning to eat with relish (not the hamburger kind). Given that both Canadians and Australians are largely descended from British settlers, it seems likely that the word is originally English. Its use is not confined to Scotland, and tuck shops are a regular feature in comics such as the Beano and Famous Five books, which have their roots firmly in 50s British culture.

At my secondary school (equivelant to US high school) the tuck shop was run by volunteer third year (~14 year old) pupils.