Начал играть на профессиональном уровне за ХК «Кладно» из родного города. Перед сезоном 1996/97 вместе с Мартином Прохазкой и Отакаром Вейводой, партнёрами по звену в «Кладно» и сборной Чехии, перебрался в AIK, выступающий в Шведской хоккейной лиге. Однако через год оба хоккеиста покинули команду: Прохазка подписал контракт с клубом НХЛ «Торонто Мэйпл Лифс» летом 1997, а Вейвода перед сезоном 1997/98 получил тяжёлую травму. Патера в 1998 году уехал в Чехию и стал игроком «Всетина» из местного чемпионата.
Всего через полтора года его задрафтовал «Даллас Старз» и Патера отправился в НХЛ. Но он провёл только 12 игр за «Звёзд», после чего вернулся в ХК «Всетин». В межсезонье Павел Патера подписал контракт с «Миннесотой Уайлд», но ему снова не удалось закрепиться в Северной Америке. Отыграв лишь 20 матчей, он остаток сезона провёл в низшей лиге, в клубе «Кливленд», а потом решил переехать в Европу. После трёх матчей за родной «Кладно», заключил соглашение с командой «Авангард Омск» из России.
С 2001 по 2004 годы Павел Патера играл за «Авангард» и был одним из первых легионеров омской команды. Вместе с Томашем Власаком и старым партнёром Мартином Прохазкой он составлял ударную тройку «Авангарда», которая по итогам сезона 2002/2003 годов стала самой результативной в российской Суперлиге. Патера поделил первое место в гонке бомбардиров с Власаком: оба хоккеиста набрали по 46 очков.
После «Авангарда» он выступал за шведский «Ферьестад», а также чешские клубы «Кладно» и «Оломоуц». В сезоне 2014/15 Патера в 48 играх за «Оломоуц» забросил 8 шайб и сделал 6 результативных передач. 4 июня 2015 года 43-летний хоккеист завершил карьеру.
