All of these are grammatically correct. It sounds like you are writing a story or narrative. In that case, I recommend looking at the surrounding sentences and reading each of these in context to see which sounds the best to you artistically.
One way to choose is to vary the length and complexity. If you have several long and complicated sentences, then the last one may be the best for its simplicity. If your other sentences are short, then you may decide on the third.
You may also consider importance in your decision. If this sentence is key to understanding the paragraph, then it should stand out from the others (either by being long and poetic or by being abrupt). If this sentence builds to the next or is a supporting detail, then it should blend in.
Finally, word emphasis can change depending on order and tone. Put the most important word first, and the second most important word last.
He relishes feeling the watch in his hand, cold and sturdy.
The first three sentences leave the reader with the impression of the word "relishes" and "sturdy" more than anything else. My first mental image is of a man's face as he contemplates and enjoys the feeling. My second mental image is of a watch that is firm and has some weight to it. If you wanted to draw attention more to the coldness than the sturdiness, you should switch the two words so that cold comes last.
The watch feels cold and sturdy in his hand.
This last option imparts on the reader something completely different, the idea of watch in hand is key here, whereas the adjectives are secondary and the enjoyment is not even included. My mental images are of a watch, and then of it being grasped as it is picked up or held.
He relishes in the cold, sturdy feeling of the watch in his hand.
The sentence that Anton suggested provides a mix of those two ideas. I have the mental picture of satisfaction, and then the concrete image of a watch being held in a hand.
So really, it depends on what's important and what sounds/feels best to you. This is an artistic choice, so it cannot be wrong.