My S4 used to have a really, really hard time starting up after sitting overnight (similar ambient temperature, too). Then one day I tried it without the choke for laughs, just gave it little gas, held the throttle, and pushed the starter button. Fired right up, and settled into a smooth idle almost instantly. I never use the choke now anymore.
-R.
-R.