В целом означает, что теперь кто-то связан на всю жизнь с этим человеком или предметом.

дословно это переводится как "we became his destiny". но означает это, что "мы стали для него очень важны в его жизни/для него"; "мы для него важнее всего"; "мы будем теперь всегда вместе на всю жизнь/до смерти"

Поэтический вопрос) означает, что люди нашли друг друга на всю жизнь.

"Стали мы его судьбою" - значит "мы теперь участники истории этого города": строим его, улучшаем, заботимся о нем, своими руками делаем его своим. "We have become his destiny" means "we are now participants in the history of this city": we build it, improve it, take care of it, make it our own with our own hands.

It is about Moscow. It is a famous song from a famous film. It means this. Their lives as lives of all the people who live in this city is a part of the life of the sity itself. They moved to Moscow and became its part. What happenes in ther lives from now on happens in the life of the city. Это как в песне Агузаровой: "Город живёт жизнью своих людей".