Re: need to have been
"If I were giving advice or talking about immigration formalities, I would say it refers to becoming a Ukraine citizen in the future after a person has lived in Ukraine for 5 years."
I agree with you on that.
However, in discussing someone who has already become a Ukraine national, then you would put it as "He had to have been living in (the) Ukraine for 5 years before becoming a Ukraine national", or "He had to have lived..."
I'm not a teacher of English, but I have spoken it for (almost) all of my life....