Je suis également gênée par votre tournure de phrase.
Vous diriez par exemple « Un homme au caractère bien trempé / aux yeux bleus / au sourire charmeur« .
Ici, « au » a le sens de « avec« , et permet de définir une particularité de l’homme.

Or « un homme avec le sentiment du devoir accompli  » ne veut rien dire.
Vous ne pouvez pas non plus être « étreint » par un sentiment, car il n’a pas de bras pour vous étreindre.

Si vous tenez à garder le mot « sentiment », voici ma suggestion :
Un homme qui a le sentiment d’avoir accompli son devoir.

Votre expression est bancale et ce n’est pas une question de préposition :  l’expression figée est « la satisfaction du devoir accompli ».
On peut éprouver ce sentiment ponctuellement, or dans votre phrase on a l’impression que c’est une qualité permanente de la  personne.
Je ne dirais donc pas un « homme au sentiment du devoir accompli »
Voici ma proposition :

Cet homme a achevé son travail, il est content : c’est la satisfaction du devoir accompli.

Il quitta son travail avec la satisfaction du devoir accompli.

Merci El Tonio de ces précisions à propos de « étreindre », c’est très intéressant.
Je me référais à l’expression « être sous l’emprise » de quelqu’un (car il a des bras pour vous « prendre« , vous opprimer) en opposition à « être sous l’empire » de l’alcool, la drogue, etc.

Il y a une règle pour ce genre de locution ou cela se fait plutôt… à l’oreille, si je puis dire ?
Est-ce que la règle change selon qu’on adopte un article, un partitif ou une préposition ?
Un sentiment de liberté, un sentiment de joie, un sentiment de travail bien fait, ou du travail bien fait ? Personnellement, je préfère  utiliser « de » mais les vocables « travail » et « devoir » semblent admettre l’article « du ».
Comme « un sentiment du travail bien fait », par exemple. Je trouve cependant que cela sonne mal, d’où ma question.

J’entends bien, pour la satisfaction, ça ne fait pas un pli, « du » est adopté immédiatement. Mais si je veux persister avec mon « sentiment« , existe-t-il une règle ou un moyen de bien faire à coup sûr ?  En la matière, je suis habité par un sentiment de confusion. Pourtant, en vous posant la question, j’ai, à l’égard de la langue française, un indicible sentiment de devoir accompli. Je pousserais même le bouchon jusqu’à dire : que je suis étreint par le sentiment du travail bien fait et je compte sur vous pour m’aider à ne pas faire d’erreur. Merci, en tout cas, du temps que vous prenez pour me répondre.

Je suis d’accord avec vous. Avec « de » ou « du », la phrase reste bancale et je préfère votre proposition. Merci de votre aide.

Quant à l’étreinte, elle peut être utilisée au sens figuré, métaphorique du terme, sans qu’il y ait nécessairement l’apport de bras ou de membres quelconques. Dans ce cas, un sentiment peut étreindre un être, une âme, un cœur, etc… L’étreinte est alors synonyme d’oppression. « Angoisse qui étreint le cœur » (Petit Robert). Cette figure de style est souvent employée en littérature :
« Mme Lecœur restait comme écrasée sous cette révélation, (…) l’envie l’étreignait aux flancs » (Zola – Ventre Paris).

« La comtesse, étreinte d’une émotion qu’elle n’avait point prévue, demeurait les yeux baissés » (Maupassant – Inutile beauté).

« Leur cœur (…) retient à soi son espérance étreinte » (Valéry – Charmes)
Merci, en tout cas, de votre attention et de votre précieux conseil. C’est d’ailleurs avec le cœur étreint par un ineffable sentiment de reconnaissance que je vous souhaite une belle journée.

Bonsoir,

Je dirais du.