Thermal Evolution of Spin-Polarons