The wagon hypotheses don't make any more sense than clay. You can't kill wagons in the actual game, just like you can't gather clay without a kiln.
"Oh but come on, it's minor to just pretend that you could kill them." Sure, but that's no different than
"Oh but come on, it's minor to just pretend that you can gather clay anyway."
If you don't insist on strict possibility, then there are dozens of answers already.
If you DO insist on strict possibility, then there are still no answers that I've heard.
It is assumed wagons were created at the beginning - before they were solely used by merchants, they were pulled around by the now-extinct Cave Horse in a symbiotic relationship. The wagon grew cave moss (it's made of a wood-like material, seriously), and the Cave Horses turned around on their long, rope-like tails to eat said moss without releasing the wagon.
Dwarves were the first to "tame" wagons. Due to their unusual nature, said taming was actually taming of the Cave Horses. After successful taming of the wagon, dwarves began "butchering" them by killing the Cave Horses connected to them to acquire Wagon Wood. Unlike most remains, Wagon Wood is viable for construction (we already knew this), which was used to create a Carpenter's Workshop and to create the First Axe.
The First Axe was used to fell underground trees - eventually, instead of something random like a goblin cap statue or a tunnel tube flute, a dwarf created the First Pick out of solid wood. Despite being made of wood, it could mine through stone, connecting the link between The First Pick and The Start.