Принцип тот же: термины типа холм, ручей, озеро, село, деревня пишутся со строчной буквы, если относятся к объектам, соответствующим их языковому значению, и пишутся с прописной, если становятся частью названия, обозначая иные, не соответствующие их значению объекты, ср.: Кузнецкий мост и улица Кузнецкий Мост, Большое озеро и деревня Большое Озеро, Красное село и город Царское Село, гора Высокая и деревня Гора Услань. Есть редкие случаи, когда термин, сохраняя свое значение, становится частью официального названия, например в России довольно много деревень, называющихся Новая Деревня. Подробнее см. в правилах употребления прописных и строчных букв в географических названиях. 

Тире уместно. Если речь о географическом названии, то нужно писать без кавычек: Черный холм (о названии холма) или Черный Холм (о названии местности, например).

В «Русском орфографическом словаре» РАН слово вади  зафиксировано как несклоняемое существительное pluralia tantum (употребляющееся только в формах множественного числа). Правильно: Песчаный холм переходит в упомянутые вади, которые делят некрополь пополам.

Сочетание асфальтовая дорога не ошибочно: «Большой академический словарь русского языка» (Т. 1. М., СПб., 2004) фиксирует у прилагательного асфальтовый оттенок значения 'покрытый асфальтом', например: Асфальтовая дорога огибала каменистый холм. К. Паустовский, Дым отечества.

Верно: в городе Холме (как и в городе Орле).