Koordynował prace nad pierwszą strategią rozwoju województwa. Stworzył tzw. Małopolską Listę Szans, unikatową w skali kraju, dzięki której mieszkańcy regionu mogli współtworzyć tę strategię. Był także inicjatorem powstania pierwszego w Polsce portalu regionalnego Wrota Małopolski. Ponownie wybrany marszałkiem w 2006 r., pełnił tę funkcję do 2010 r.
Odznaczony m.in. Złotym Krzyżem Zasługi, Krzyżem Kawalerskim, Krzyżem Oficerskim Orderu Odrodzenia Polski, Medalem Komisji Edukacji Narodowej, Złotym Medalem za Ratowanie Życia i Ochronę Mienia oraz Srebrnym Medalem 600-lecia Odnowienia Akademii Krakowskiej. Za szczególne zasługi dla samorządności w Polsce wyróżniony Nagrodą im. Grzegorza Palki (tzw. samorządowym Oskarem). W 2010 r. podczas Kongresu 20-lecia Polskiego Samorządu otrzymał Różę im. Franciszki Cegielskiej – nagrodę za szczególne zasługi dla samorządności w Polsce.
Marek Nawara zmarł nagle w swoim domu pod Krakowem, 25 maja 2011 r. Miał wtedy 56 lat. Został pochowany w Alei Zasłużonych na Cmentarzu Rakowickim w Krakowie.
Radni województwa odznaczyli go pośmiertnie Złotym Medalem za Zasługi dla Województwa Małopolskiego, m.in. wprowadzenie dotacji na rzecz ratowania zabytków w Małopolsce, wspieranie Ochotniczej Straży Pożarnej w regionie i kompleksowe podejście do problemów transportu publicznego.
