The rules take a chaotic, simultaneous situation and break it up with the initiative roleroll, with each PC/NPC acting on their 'turn'. This is what gives the battle a logical consistencyconsistency; otherwise, it would be madness.
So, although each PC/NPC isn't really waiting in a nice orderly line to state their actions, that is the way it is handled. Without that the battle would be awful to try and control.
So, yes, by the time the Cleric takes their turn, the Paladin has taken damage and they can cast their spell.
This is where reactions are important as they allow a PC/NPC that has already had their turn in that round respond to events that happen afterwards.