"We are looking for Khreshchatyk Street."
Translation:Ми шукаємо вулицю Хрещатик.
With a flexible word order in Ukrainian I'm guessing that Ми шукаємо Хрещатик Вулицю is also correct?
Хрещатик is the proper name of the street. Whereas in English proper names precede common nouns, in Ukrainian they come after. In English you can't say "Avenue Madison," and in Ukrainian you can't say Хрещатик вулиця.
Here Хрещатик is being used as a name and should actually be in quotation marks (вулиця "Хрещатик"). So, "We went toward Khreshchatyk Street" would be, Ми ішил до вулиці Хрещатик. But if you drop the word "street," Khreshchatyk no longer functions as a name, and declines like any other noun: Ми ішли до Хрещатика. Remember, though, that in the accusative, Хрещатик doesn't change, so Ми шукаємо Хрещатик won't either.
The main word in the compoud is вулиця, so it's the only one affected.
E.g. if you had a compound "mom's book" - книжка (Nom.) мами (Gen.) - you would only decline книжка but not мами: Я шукаю книжку мами, У мене немає книжки мами.