From what you've said, the WH IS working, and you either have a distribution problem or a fixture problem. Is the only fixture that can't get hot the shower? What about other things in the house? What kind of shower control valve is it? Do you know if it is a thermostatically controlled valve, a pressure balanced valve, or an old, basic valve?
Do you have a recirculation system? Have you changed any faucets recently? If you say shut the water off to the kitchen sink at the shutoffs in the cabinet, does it get better? What about doing the same thing for the vanity(s) in the bathroom(s)? Some single handle valves when they fail internally can cause the hot/cold to cross-over. You may have that situation. If so, then finding the offending one is the next task. Repairing or replacing that one will solve your problem.