Papac rozpoczynał piłkarską karierę w klubie NK Široki Brijeg. W 2000 roku w wieku 20 lat zadebiutował w tym klubie w pierwszej lidze bośniackiej. Po roku gry w ojczyźnie Papac wyjechał do Austrii, by zostać zawodnikiem tamtejszego FC Kärnten. W zespole tym od początku grał w pierwszym składzie w 2002 roku zajmując 5. miejsce w lidze, a w 2003 dochodząc do finału Pucharu Austrii, w którym jego klub uległ 1:2 Austrii Wiedeń. Jednak dzięki zdobyciu przez Austrię mistrzostwa Papac w sezonie 2003/2004 wystąpił z Kärnten w rozgrywkach Pucharu UEFA. W lidze klub z Klagenfurtu spisał się jednak słabiej i zajmując ostatnie miejsce spadł do drugiej ligi.

Latem 2004 Papac przeszedł do Austrii Wiedeń. W stołecznym zespole Bośniak zadebiutował 14 lipca w wygranym 2:1 meczu z Admirą Wacker Mödling. Grał w wyjściowej jedenastce, zdobył 2 gole, a z Austrią zajął 3. miejsce w lidze. Sukces osiągnął rok później, gdy wywalczył mistrzostwo Austrii.

Sezon 2006/2007 Papac rozpoczął w Austrii, ale 31 sierpnia podpisał kontrakt z Glasgow Rangers, do którego przeszedł wraz z klubowymi kolegami Liborem Sionko oraz Filipem Šebo. Papac kosztował szkocki klub 450 tysięcy funtów.