Recent experiments have reported lower critical solution temperature (LCST) phase behavior of aqueous solutions of proteins induced by multivalent ions, where the solution phase separates upon heating. This phenomenon is linked to complex hydration effects that result in a net entropy gain upon phase separation. To decipher the underlying molecular mechanism, we use all-atom molecular dynamics simulations along with the two-phase thermodynamic method for entropy calculation. Based on simulations of a single BSA protein in various salt solutions (NaCl, CaCl2, MgCl2, and YCl3) at temperatures (T) ranging 283-323 K, we find that the cation-protein binding affinity increases with T, reflecting its thermodynamic driving force to be entropic in origin. We show that in the cation binding process, many tightly bound water molecules from the solvation shells of a cation and the protein are released to the bulk, resulting in entropy gain. To rationalize the LCST behavior, we calculate the ζ-potential that shows charge inversion of the protein for solutions containing multivalent ions. The ζ-potential increases with T. Performing simulations of two BSA proteins, we demonstrate that the protein-protein binding is mediated by multiple cation bridges and involves similar dehydration effects that cause a large entropy gain which more than compensates for rotational and translational entropy losses of the proteins. Thus, the LCST behavior is entropy-driven, but the associated solvation effects are markedly different from hydrophobic hydration. Our findings have direct implications for tuning the phase behavior of biological and soft-matter systems, e.g., protein condensation and crystallization.