I don’t really understand what bothers you, the uses of these tenses are the same as for all verbs, except that as a semi-auxiliary, the semantic information is transferred to the verb it modifies, but it is the same as for any other semi-auxiliary, e.g. vouloir or pouvoir.

• devait is the past imperfective (or inaccompli) for situational information, it denotes that in the frame of the sentence, the subject had an obligation, without specifying if he complied to it

  Il devait partir à Rome et sa femme voulait venir.
  Il devait cuisiner l’​osso bucco mais il a oublié.

• a dû is the past perfective (accompli), it denotes that the subject did the thing he had to do:

  Il a dû partir à Rome précipitamment.
  Comme il ne restait plus que de la viande hachée, il a dû faire une bolognaise à la place.

So devait denotes a context, whereas a dû denotes an action. Thus, a dû implies that the action has been done whereas devait does not, but it is more a side-effect than the real point of this choice of tense.

My suggestion to avoid some of the ambiguity in the translation would be to say “He was supposed to leave for Rome…” for “Il devait partir à Rome…” That way the “He had to leave for Rome immediately” can be definitive.

When devoir is given an “accomplished aspect” using passé composé (or any other composed tense), it expresses “fulfilment” of a necessity. By the course of events, something just ceased to be necessity. It means that the person did what he had to do, and strangely (I concede) it cannot mean that the problem solved by itself (this is pretty much specific to devoir and a few other modal-like verbs).

For example, “il a dû se présenter devant le juge” means he had to and did appear before the judge. If the problem solved externally, one would use imparfait, or provide an explicit reason introduced, for example, as follows:

Il a cru devoir se présenter devant le juge, jusqu’à l’arrivée d’un nouveau temoin.

This is possible because croire (similarly vouloir) relate the subject’s thoughts or wills, which are expected to adapt to the course of external events. Verbs like devoir or pouvoir or savoir are different because the subject isn’t taking any action or position or decision and is just passive. I’d say this is what makes them special. In particular, similar to “il a dû”, the sentence “il a pu/su faire quelque chose” also means that he could/knew how to do it and did it.

Note: it can get even more confusing since devoir may also express likeliness, not only necessity (and pouvoir may also express possibility).

— Tu sais pourquoi Pierre n’est pas là ?
— Il doit être occupé… ou il a dû partir à Rome !

In this context you can forget all the above, as the reply is just a guess about the reasons (English would use must: “he must be busy… or he must have left for Rome”.)