Have finally found out the movements of the 2/24th
Jan 1873 to Dec 1873 Warley, Essex
Dec 1873 to June 1875 Aldershot
June 1875 to June 1877 Dover, Kent
June 1877 to Jan 1878 Chatham, Kent
March 1878 to March 1879 South Africa
Given the above and the fact that their base was at Brecon, he could presumably have been there at various times to meet Mary Ann, get her pregnant (summer 1876), marry her (Oct 1876), and register the birth of the first child (born 22 March 1877, registered 9 April 1877).
Sometime during the following year he then went missing but was caught, and got Mary Ann pregnant with the 2nd child (around March 1878) before being sent to South Africa (March 1878).
The birth of the 2nd child around 65 miles away from Brecon in Cardiganshire on 28 December 1878 was registered by Mary Ann on 8 Feb 1879, as John Richard Packman, father Walter Robert Packman, coachman. However, it appears likely that the birth date was false as well as the name... his baptism record says DOB 12 Dec 1879, the 1939 register says 12 Dec 1880, so I'm inclined to think that his actual DOB was 12 Dec 1878 but changed to avoid a fine for late registration (8 Feb 1879 being 6 weeks to the day after 28 Dec 1878).
This all ties in with Walter being in the UK until March 1878 when the 2/24th went to South Africa, so he could well have been at Isandlwana (with Chelmsford), returning home afterwards and being discharged (as an invalid) in June 1880.
Presumably he used the name Packman in the 1881 and 1891 censuses to keep his pension, despite registering all the later children as Leigh, and having them all - including John Richard Packman - baptised as Leigh. Strangely, Walter was baptised himself in 1884 (aged 39), though he had already been baptised - twice - as a child.
We still have the puzzle as to where he was from 1861 (Kent) until 1876 (Brecon) and how the two join up. Are there any records not online that might help us further?