When did the Skutatoi come around?

[Robert Vermaat]

Were units armed and equipped with the stuff in my quote in the 4th and 5th century Byzantine army?

There was no 4th and 5th century Byzantine army, there was only a 4th and 5th century Roman army!! 8)
Yes, of course they were equipped with scuta, by then every shield was called a scutum, right? Scutati is nowadays translated with 'shieldbearers' (like in Vegetius), which is also odd, since infantry is usually bearing shields.

The Notitia Dignitatum has only two units of scutati: Scutati civii Romani, in Egypt, and the Scola scutatorium tertia.
More units are called scutarii though:
Mauri scutarii
Scola scutariorum prima
Scola scutariorum prima
Scola scutariorum secunda
Scola scutariorum secunda
Secundi iuniores scolae scutarii
Scola scutariorum clibanariorum
Scola scutariorum sagittariorum
Scutarii (mentioned 6 times)
Scutarii seniores
Primi scutarii
Secundi scutarii
Scutarii Aureliaci
Scutarii Illyriciani (mentioned 5 times)
Scutarii indigenae Pafenses
Primi scutarii Orientales