There is one origin story of Shudras attributed to Vishvakarma. This will at least give an origin story to the artisans among Shudras, though not to others like cowherds, boatsmen, etc.
There is one story of Vishwakarma and Ghrtachi apsara cursing each other to be born on earth as a Brahmin and Shudra (cowherd caste) respectively. With their union these 9 sons were produced.
The story is found in the Brahmavaivarta Purana Brahma Khanda Chapter 10
Thereafter the lustful woman became pregnant with well-nourished foetus and she gave birth to nine beautiful sons at that very place. O Saunaka, Visvakarma, imparted adequate training in various arts to all his sons and they became intellects, competent valorous and wise. He then entrusting then the jobs of gardeners, blacksmiths, conch-makers, weavers, potters, carpenters, gold smiths and painters and also blessed them variously. He then dedicated all of them to the universe and discarding the human body, Visvakarma went to his heavenly abode.
Thereafter, there is a whole list of the origin of other Shudras. Since it is too lengthy, I’m citing a few examples only:
- Painter + unchaste Shudra woman = Balcony maker
- Balcony maker (m) + Potter (f) = home maker/ mason
- Potter (m) + mason (f) = oil crusher
- go on to describe other Varnasankaras
Other Shudras whose origin is not mentioned are (yes there is overlap):
O best of the Brahmanas, the cowherds, barbers, sweet meat sellers, the weavers, the black smiths, the gold smiths and the traders are known as sat-Sudras
The basic point of this answer is that for the craftsmen, Vishwakarma was their originator. They still revere him in many parts of India and call themselves the Vishwakarma caste.