I agree that the Bakerloo won't be busy then; I find the Vic unpredictable in terms of passenger density these days.
I'd suggest 15/20 minutes is a bit optimistic for one of the not-very-speedy hire bikes. Even on my own less sluggish bike, and knowing the way to wiggle through the back streets to take a relatively straight-line route from Waterloo Bridge to Kings Cross, I doubt I'd make it station-station in 15 minutes. (Maybe it's me that's sluggish...) And the bike docks aren't right by Kings Cross station - the quickest is probably the one tucked in one of the little side streets opposite the station, if you know where it is...
If you don't mind a slower journey than the tube, there's always a bus. (Well, two actually - a change is needed now, somewhere between Aldwych and Euston, depending, since the very useful through journeys on the 59 were cut back to Euston. But even with the change, it can be done in 30 minutes ... though it isn't always...) It's annoying that KX/StP to and from Waterloo is the one major station to station link in London which has neither a direct bus nor a direct underground link.
If you do use the Bakerloo/Vic route - probably the safest if you have any time pressures at all - can I concur with the earlier post which said to make sure you get off at the rear end of the Vic on arrival at KX Underground. That way leads straight up into the open air in front of KX station; following the signs they want you to follow, via the new passageways, means a five-minute (at least) diversion before you get to your KX mainline platform.