Мне кажется тут все очень просто. Если эту улицу строили как "Проспект Карла Маркса", то такое название улице и носить. Это своего рода дань тем кто ее строил и тем кто ее так называл, и не важно какой политический контекст у этого названия сейчас. Это память, и помнить нужно не только хорошее, но и плохое.

Также нужно понимать что ЭТУ улицу строили после войны, и всяческие "доисторические" мостовые в этом районе нынешней улицей считаться не могут.

Хотите "Проспект Воинской Славы" - постройте его, да так постройте, чтобы не стыдно было называть его таким именем.