On the one hand, your analysis of sort of 'semantic origins' of the best of messengers is probably correct: the best messengers out of all possible messengers.
However, the meaning of Kim and Jane were not the best of messengers is simply this: they were not very good messengers.
Moreover, Kim and Jane were not the best messengers has, as best as I can tell, the same meaning—at least as written, and if no special intonation is used (see below).
If you wanted to convey that Kim and Jane were perhaps still very good messengers, just not literary the very best ones, then you'd need to rephrase in some way and perhaps use special intonation:
Kim and Jane were not the best messengers, but they were very good ones nonetheless.
Note that in this case it is not semantically possible to use the of-construction. The sentence
Kim and Jane were not the best of messengers, but they were very good ones nonetheless.
sounds like a contradicition, at least to my ear.