Would "The interview is with Mark" be a valid translation?
"Це інтерв'ю є з Марком" would be the Ukranian sentence then.
"є" is not needed.
Apparently, to convey that meaning it needs some kind of pause: "Це інтерв'ю - з Марком"
So names in Ukrainian also take instrumental forms? It's not only with objects?
Not only instrumental, but other cases too, for example, Я бачу Марка (accusative).