Why "měl + verb" is sometimes translated as "should + verb", and sometimes as "should have + verb"?
It depends on the tense/mood of the Czech sentence. (Look carefully at the verb in the Czech sentence.)
present tense -> should + infinitive
past tense -> should have + participle
present tense -> should eat
past tense -> should have eaten
Note that in English there is no past tense of the verb "should" itself, so English works around that by changing the tense of the following verb (from the infinitive to the perfect infinitive).