Začátky se datují od r.1974 kdy hrál za příravku Slavii Praha. Když v osmdesátých letech přišel do slávistického B týmu, hrál na postu stopera. Jenže v B týmu se tou dobou právě rozehrával po zranění reprezentační obránce Luboš Kubík, a mladý Kuka musel uvolnit své místo v obraně. Poté začal hrát v útoku.
Své první ligové zápasy odehrál až na vojně v dresu RH Cheb, v sezoně 1987/1988. Do Slavie se vrátil v roce 1989. V roce 1991 koupil Slavii Boris Korbel, který neváhal utratit peníze za kvalitní hráče. Právě vedle nich se Kuka stal opravdovou hvězdou. V sezoně 1992/1993 nastřílel 23 branek, ale bohužel o titul krále střelců ho připravil útočník Slovanu Bratislava Peter Dubovský.
V zimě roku 1993 odešel Pavel Kuka do 1. FC Kaiserslautern, kde v té době působil i Miroslav Kadlec. S Kadlecem Kuka hrál i na Mistrovství Evropy ve fotbale 1996 v Anglii, kde si zahrál dokonce finále proti Německu. Stříbrnou medaili pak přebíral na stadionu ve Wembley spolu s ostatními reprezentanty od anglické královny Alžběty II. Po tomto úspěchu měl spoustu nabídek ze zahraničí, hlavně z Anglie. Zůstal ale v Kaiserslauternu, který strávil následující sezonu ve 2. lize. V Německu hrál také za 1. FC Norimberk a VfB Stuttgart. V roce 2000 spolupracoval na vytvoření počítačové hry FIFA 2001 a na podzim se vrátil do Slavie. Přestože neodehrál celou sezonu, stal se druhým nejlepším střelcem ligového ročníku 2000/2001 a za prvním Vítězslavem Tumou zaostal pouze o jeden gól.
Poslední ligový zápas odehrál ve 29. kole ročníku 2004/2005 na hřišti Baníku Ostrava dne 28. května 2005. Když jej ve druhém poločase střídal Pavel Fořt, tleskali mu i příznivci Baníku. Svůj poslední zápas před domácím publikem sehrál o tři dny dříve na stadionu Evžena Rošického na Strahově v rámci 30. kola proti Zlínu. Kompletní 30. kolo se předehrávalo. Slavia tehdy nemohla Zlínu dlouho vstřelit gól, několik šancí zahodil i Kuka. V druhém poločase se k míči dostal Lumír Sedláček, jeho střela se otřela o Kukovo stehno a zapadla do pravého horního rohu branky. Slavia tehdy vyhrála 1:0.
Po skončení aktivní kariéry se stal generálním manažerem klubu Marila Příbram, po půl roce ale na vlastní žádost odešel. Zahrál si také fotbal na nižší úrovni, když v roce 2006 nastupoval za klub SK Marila Votice, jemuž pomohl k historickému postupu do Divize A. Jeho poslední působení bylo v klubu I.B třidy – FC Jílové.
V české nejvyšší soutěži nastřílel 104 branek, 50 gólů dal v německé Bundeslize a dalších 10 ve druhé nejvyšší německé soutěži.
Kuka reprezentoval Československo a následně Česko v 88 utkáních, dal celkem 29 branek. Jeho největším reprezentačním úspěchem je již zmíněné EURO 1996, ale zahrál si také na EURO 2000, které se konalo v Nizozemsku a v Belgii.
Své poslední reprezentační góly vstřelil v utkání kvalifikace na Mistrovství světa 2002 proti Severnímu Irsku, které Češi vyhráli 3:1. Dva góly dal Kuka, jeden jeho nástupce v českém útoku Milan Baroš. Do baráže o postup na MS proti Belgii nezasáhl kvůli zranění. Na mistrovství světa si nikdy nezahrál.
- mistr Německa: 1998
- vítěz Německého poháru: 1996
- vítěz Českého poháru: 2002
- finalista ME: 1996
- člen Klubu ligových kanonýrů