Велько Паунович народився 1977 року в Струмиці у колишній Соціалістичній Республіці Македонія. Розпочав займатися футболом у школі клубу «Партизан». Дорослу футбольну кар'єру розпочав 1994 року в основній команді того ж клубу, в якому грав до 1995 року, взявши участь у 13 матчах чемпіонату.
У 1995 році молодий футболіст отримав запрошення від клубу «Атлетіко», проте спочатку він грав у складі її фарм-клубу«Атлетіко Марбелья», а з 1996 року прийшов до основної команди мадридського клубу, проте не відразу став основним гравцем клубу, багато ігрового часу проводив у другій команді, а в 1998 році сербського півзахисника віддали в оренду до іншого іспанського клубу «Мальорка», у складі якої він став володарем Суперкубка Іспанії з футболу. Пізніше кілька разів футболіст повертався до «Атлетіко», в якому рахувався на контракті до 2005 року, проте керівництво мадридського клубу віддавало Пауновича в оренду до інших клубів — іспанських Реал Ов'єдо", вдруге «Мальорка», «Тенерифе», та німецького «Ганновер 96».
У 2005 Велько Паунович став на постійній основі гравцем іспанського клубу «Хетафе», в якому грали на 2007 року. У 2007 році серьський півзахисник грав у складі казанського «Рубіна», після чого повернувся до іспанського чемпіонату до клубу «Альмерія». У другій половині 2008 року Паунович повернувся до складу «Партизана». На деякий час футболіст завершив виступи на футбольних полях, проте в 2011—2012 роках грав у американській команді «Філадельфія Юніон», після чого остаточно завершив виступи на футбольних полях.
У 2015 році Велько Паунович став головним тренером клубу Major League Soccer«Чикаго Файр», у якому працював до 2019 року. У 2020—2022 роках сербський тренер очолював англійський клуб «Редінг». У 2023 році Паунович очолював мексиканський клуб «Гвадалахара».