You recall Theodora mentioning the golems and elementals of that region as being a source for these shards.
Quest Text Edit
The machines made themselves known to us during our initial forays into the Searing Gorge. Upon further investigation we discovered that they were being imported from Burning Steppes, possibly Blackrock Depths. That is what we need you for, <name>.
Your first task is to venture to the Burning Steppes and recover elemental shards from the rock automatons and lesser rock creations of the region. Once you have collected a sufficient amount, return to me and I shall determine their source of origin.
The shards drop from the golem-like War Reavers and the rocky Greater Obsidian Elementals in the Burning Steppes.
Experience and Gold