I can't find the British order, but the Canadian Army first ordered it to be painted on 11th April 1944. Something worth noting is that the Canadian Army ordered it to be painted with one point of the star to be pointing toward the front of the vehicle, so it looks 'wonky' in photos. The British almost always painted it the traditional way, 'resting' on two points, though there are examples of it being painted in the Canadian manner.
I've seen it mentioned in forums that it was introduced in 1943 for the invasion of Sicily, but not seen anything concrete.
Stars certainly were painted in Italy, but don't seem to be anywhere near as common as in NW Europe and there are photos of vehicles all the way up on the Austrian border in 1945 still painted with the RAF-style roundel.
In Burma some stars appeared on upper surfaces in 1944, but by 1945 they were universally applied and were LARGE.