Attributive modifiers of this sort are extremely common, though the ones in your examples are not headed by past participles - there are no corresponding verbs with the same interpretation:
*We blood the veins. (make so that they have blood in them)
*We billed our snowman. (made our snowman with a bill)
*The composer noted his melody well. (make so that it has notes)
Besides, cold, small, and five could hardly modify verbs.
These seem to be more along the lines of adjectives (that denote properties) that have been made from nouns - denominal adjectives.
Some, like the ones you've listed, have pretty much the same interpretation (1) as attributive modifiers or (2) as part of a post-head prepositional phrase headed by with.
a open-minded man = a man with an open mind
an ill-fated voyage = a voyage with an ill fate
Some have an implied meaning and do not readily allow the prepositional version.
a one-sided conversation = a conversation with one side doing most of the talking / overruling the opposing party(parties)
a conversation with one side = (not a common expression)
Some have different interpretations depending on whether they are attributive modifiers or part of a prepositional phrase.
a left-handed man = a man who uses his left hand for dexterous tasks
a man with a left hand = a man who has a left hand
Some are euphemisms.
a wide-eyed youngster = a credulous/innocent youngster
a heavy-handed response = a clumsy/tactless/oppressive response
Are the above idiomatic? Yes, the sheer number of them, especially of the three types having idiomatic meaning (that cannot be derived from the conjoined meanings of their elements), would suggest that they are an integral part of the English language.
As far as preference goes, as Edwin Ashworth noted in the comments, some may strike particular English speakers (or English speakers in general) as unnecessary or ill-advised.
?an important-friended man [a man with (an) important friend(s)]
?a fresh-flowered cemetery [a cemetery with fresh flowers]
?a large-tabled room [a room with a large table]
This would suggest that the construction, though common enough, is not a standard formula that works for any adjective-noun combination which may be found in a prepositional phrase acting as modifier in a noun phrase.
As far as preference is concerned, the question only arises with the type where the attributive modifier and prepositional versions have the same meaning - in all others, the attributive is mandatory if the desired meaning is to be achieved.
The attributive modifier is generally preferred where the attributive version has attained wide acceptance, such as with ill-fated: there are 120 examples of the attributive version in the Corpus of Contemporary American English versus 0 of the prepositional version, though it would be readily comprehensible and even grammatical to any native speaker.
Some are in between, though still the attributive version seems preferred: fat-faced (19 in COCA) and with a fat face (4), or chubby-cheeked (28) and with chubby cheeks (5), or long-legged (385) and with long legs (71), or sunken-cheeked (7) and with sunken cheeks (6), or wide shouldered (39) and with wide shoulders (23).
A very few only allow the prepositional verison: fresh-flowered (0) and with fresh flowers (48). These are usually those that refer to things or places, not people or animals/plants/etc.
