Red of course was the colour [stupid spell check of course colour has a u!) of the British Armies uniform, so the reds are coming etc generally goes to the red coats. I know in OZ i have heard “turning to the outback red” before in a poem referring to the soldiers but damned if I can remember it.
Never heard of that particular phrase but on older maps, countries that were part of the British Empire were coloured pink. So maybe we were “turning the map pink”
“Paint the map red” is a quote attributed to Cecil Rhodes. It refers to the colour of British possessions on maps. It has nothing whatsoever to do with Redcoats.
I originally heard paint the map red or something like paint the world red from a British Antiques appraiser on the telly. He was appraising a piece of Campaign Furniture. He was saying “it was used back when Britain was painting the map red”. It caught my ear because such simple worlds means volumes when you think of the British Empire’s bloody creation.
Maybe not universal, but on British maps it was certainly the convention, and very common, to color the British Empire pink (and, later, the British commonwealth, or at least the bits, like Australia and Canada, where Queen Elizabeth is still queen). I have seen lots of maps like that in my time, and, although I do not know the specific phrase mentioned by the OP, I have often heard a phrase like “the pink (or red) bits on the map” used to mean (former) British possessions. I think most other older British people would understand it too. I am not sure about youngsters.
The cartographic convention was in use long, long after the British army ceased to wear red uniforms (indeed, I am not sure that it is not still in fairly wide use on British made maps). I see no reason to think that there is any connection.
If it was “To paint the town red” it would have been a reference to the famous hooligan, Henry de la Poer Beresford the “Mad” Marquis of Waterford in 1837. (He literally went nuts with red paint - got the town toll booth, several buildings and painting someone’s horse’s heels with aniseed and then setting the bloodhounds on him.