The idea here is among all the tuples with the same digits only the one sorted lowest needs to be checked. That sort/union operation is much faster than the total^2 operation so it is worthwhile:
SumLimit = 450 First@(FromDigits /@ Select[Union@(Sort /@ Tuples[Range[0, 9], {Ceiling[SumLimit/81]}]), Total@(#^2) > SumLimit &]) {0.608404, 799999}
Faster still, here we avoid generating all the tuples to begin with.
nd = Ceiling[SumLimit/81];81]+1; First@Sort[ FromDigits /@ Select[ #[[2]] & /@ Nest[( Flatten[ Map[(next = #[[1]] + 1; {next, #} & /@ ({#[[2]]}~Join~ Table[ Join[#[[2]] , ConstantArray[#[[1]], i ] ], {i, 1, nd - Length[#[[2]]]}])) & , #, 1], 1]) & , {{0, {}}} , 10] , Length[#] == nd && Total[#^2] > SumLimit&]] // Timing {0.140401, 799999}