This concept of absolute, perfect newness is very old in itself, dating back past medieval English to the Old Norse, in which its form was span-nyr, from spann, “a chip,” plus nyr, “new.”
The allusion is to the newness of a chip freshly cut by the woodsman’s ax.
Variants such as spang-new, spanking new, etc., are merely inventive expansions giving additional emphasis, as is the longer term spick-and-span-new.
In this last, spick is identical to spike, and the allusion is to a spike just off the blacksmith’s forge.
The later extension of spick-and-span to imply neatness or cleanliness, of course, is with reference to the appearance of newness.
Brand-new (bran-new) refers to the newness of something, such as pottery, perhaps, fresh from the fire (brands), and this has led to the sometimes-heard bran-span-new.