Translation:They used to walk more when they did not eat.
I must respectfully disagree. If the sentence had the words "as much" at the end, I would say your translation was acceptable. However, the phrase "when they did not eat" means that they ate nothing for some indefinite time period, which theoretically could have been for months! Patently, this is absurd. This inference also begs the question: If they "walked more when they did not eat," then did they stop walking when they started to eat more again? The only way this sentence sounds natural is "They walked more when they hadn't eaten" or "They walked more when they hadn't eaten as much."
No, because "ellos caminaban más cuando no comieron" would mean that one day, they were walking more, when all in a sudden, they didn't eat. If you use both tenses in a sentence, the imperfect will be used to explain the setting and the preterit will be a punctual and once-occurring action, that interrupted the setting. In that sentence, it seems that both clauses are bound and occur at the same time. One is the consequence of the other.