Unusual to have a problem with the cold water in the kitchen as its usually the first take off and normally you dont get an airlock problem on this one. Did you turn the mains tap back on to the same position as before??
Overall- sounds like airlocks in the system. When you turn the water supply back on do it with all the taps in the on position- only turn them off when they are flowing properly. That normally gets rid of airlocks. You might need to isolate the incoming water again, drain down and then refill the system again.
The overflow is odd as you say it only happens witha downstairs hot tap?? I would check the hot water supply tank in the loft anyway and check that the float is closing the valve properly.