"We are looking for Khreshchatyk Street."
Translation:Ми шукаємо вулицю Хрещатик.
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.
Yes, in Polish and Czech, for example, one can omit the pronoun. Same in Italian and Spanish. But in Ukrainian and Russian we don't do it.
We sometimes do drop pronouns, but it's more in the area of slang and spoken language. We often do it asking "do you want" questions e.g. "Хочеш в кіно?" (two words are skipped, "ти" and "піти").
But otherwise no, we keep the pronouns, unlike Czech :)