>Was it possible to wage winter warfare in regions with milder climates such as Palestine, Carthage, or Sicily?

The issue is not just weather. You still see cold winters in places like Palestine, but there is also a dearth of food and fodder; many forces throughout history relied on foraging, stealing, buying, or otherwise obtaining food from local sources as they moved. There tends to be rather less of it in winter, which makes supply more difficult. Winter campaigning isn't impossible, but even with a real logistics system, it is more difficult, and there are often other administration issues with maintaining a force year-round. There was an expectation for many forces that, outside of a campaigning season, they would have time to go home, or otherwise find somewhere to become established and start to prepare for the next campaign. Transport, supply, maintenance, etc are all more difficult in winter, and you also have additional costs.

Winter campaigning was done inconsistently for a long time, from the Vikings, to mercenary companies in medieval Italy, to various Roman campaigns, but consistent winter fighting is very modern, and was still influencing plans (especially concerning agricultural workers) in the 20th century. It became less of an issue thanks to industrial and technological factors, so there isn't one point you can definitively identify as the year, but around the 19th century, certainly the latter half, is when armies began to campaign regardless (often with awful results).