It's because of that a Pokémon essentially need an egg group to breed with other compatible Pokémon. All genderless Pokémon, except Legendaries and baby Pokémon can breed with Ditto. But every genderless Pokémon has an egg group.
Which means, a Pokémon having no egg group cannot breed even with Ditto (Such Pokémon doesn't exist too! Even Legendaries and baby Pokémon has an egg group called Undiscovered)! So, Gamefreak gave Starmie Water 3 type! They included it in this egg group because of this reason,
The last of three water egg groups, Water 3 is a mix of different Pokémon types, including fossil Pokémon, crabs and invertebrates.
Water 3 egg group
Starmie is based on a Starfish, which is an invertebrate. So they gave it the egg group Water 3.