It's always difficult to recommend a 'best' translation in a case like this, when there is no real context. However, I see that North & Hillard in this chapter are introducing the use of cum, about which a degree of care is needed.
You are right that Latin 'seems' reluctant to deploy pluperfects, but that's because it very often shows an approach to a sequence of actions that is different, more rigid than English (this partly explains the tendency for Latin to use fewer words than English).
In this case, as you might recognize, N&H might equally well have written 'When the citizens had almost died of starvation, relief arrived.' Then, I think, you might more naturally accept cum cives fame paene mortui essent, auxilium advenit. That's the translation which I would choose.
This is a very familiar construction in Latin when a sequence of events is being described. Caesar, for example, seems to have been very fond of expressions such as eo cum venisset . . ., 'when he had got there', and Romae cum ventum esset . . ., 'at Rome when the journey was over', or (which means the same thing) 'when they had got to Rome'. I don't know the answer supplied in the key to N&H, but it won't necessarily be the only, nor indeed the best translation.
I will leave it there so as not to confuse you, but you might like to consider what you would write if the sentence to translate had been 'relief arrived when the citizens had almost died of hunger.'