Футбольну кар'єру розпочав у «Торкі Юнайтед» 9 липня 1990 року, хоча в англійській першій встиг дебютувати ще попереднього сезону, допоміг «Чайкам» вийти до плей-оф, але виступав на фланзі нападу, провівши 93 поєдинки в чемпіонаті. 25 березня 1993 року за 70 000 фунтів перейшов до «Портсмута».
Після вдалих виступів на чемпіонаті світу за 300 000 фунтів до «Ковентрі Сіті». Через чотири місяця після цього переходу головний тренер «Ковентрі» Гордон Стракан повідомив Пола, що той не вписується до ігрової моделі команди, проте Голл вирішив залишитися в команді та поборотися за своє місце в складі, при цьому нападник наприкінці листопада 1999 року відмовився відправитися в оренду до «Порт Вейл». 18 лютого 1998 року відправився в оренду до «Бері», проте незабаром повернувся на «Гайфілд Роуд», щоб попборотися за місце в стартовому складі. Наступного сезону на поле виходив ще рідше, тому 17 грудня 1999 року відправився в оренду до «Шеффілд Юнайтед» (відзначився голом у поєдинку проти «Грімсбі Таун»)[2]. 10 лютого 2000 року був орендований «Вест-Бромвіч Альбіон», проте за підсумком жодної з цих оренд постійний контракт так і не був підписаний. У футболці «Ковентрі» відзначився ще одним голом, у воротах «Саутенд Юнайтед» у Кубку ліги[3].
17 березня 2000 року Пол залишив команду з «Гайфілд Роуд» та відправився в оренду у «Волсолл», по завершенні якої будучи вже вільним агентом підписав з клубом повноцінний контракт. Допоміг клубу через плей-оф вийти до Першого дивізіону, проте в плани головного тренера Рея Грендона на сезон 2001/02 років вже не входив. Цією ситуацією намагався скористатися «Порт Вейл» й 20 вересня запрпонував взяти в оренду нападника, але «Волсолл» заявив, що розглядатиме лише варіант з повноцінним трансфером. Наступного тижня відправився на перегляд до «Квінз Парк Рейнджерс», проте вже незабаром повернувся у «Волсолл». Зрештою 10 жовтня 2001 року залишив «Бескот Стедіум» вільним агентом та приєднався до новачка чемпіонату «Рашден енд Даймондс»[4], де виступав пліч-о-пліч з колишніми нападниками «Торкі» Скотом Партриджем та Дюейном Дербі. У команді відіграв три сезони, зіграв 112 матчів та відзначився 26-а голами. У фінальному поєдинку плей-оф Третього дивізіону проти «Челтенгему» Голл зрівняв рахунок у матчі завдяки прекрасному сольному проходу після розіграшу штрафного. Коли фінансові проблеми змусили «Решдон» задля розвантаження зарплатної відомості позбутися декількох гравців, Голл переейшов до «Транмер Роверз», за який зіграв 55 матчів та відзначився 13-а голами[5].
Напередодні початку сезону 2005/06 років перейшов вільним агентом до «Честерфілду»[6]. У новому клубі був гравцем стартового складу та найкращим бомбардиром команді, у футболці якої відзначився 15-а голами в 47-и матчах чемпіонату та кубку. 4 червня 2007 року повернувся до свого колишнього клубу, «Волсолл». Єдиним голом за нову-стару команду відзначився в своєму другому поєдинку, на останній хвилині переможного поєдинку проти «Гартлпул Юнайтед»[7].
11 січня 2008 року Голл та його одноклубник Дені Соннер перейшли до «Рексем» з Другої футбольної ліги, проте ямаєць виступав у валійському клубі лише в оренді[8]. Пол візначився дебютним голом за нову команду 9 березня в переможному (2:0) поєдинку проти принципового суперника «Рексема» — «Честер Сіті» (перший гол у тому поєдинку)[9]. Проте Голл отримав травму й змушений був повернутися до «Волсолла». У липні 2008 року підписав контракт з клубом «Ньюпорт Каунті» з Національної ліги Південь, яку тренував Дін Голдсворт[10]. Проте вже в жовтні 2008 року сторони домовилися про розірвання угоди. А в листопаді 2008 року Пол приєднався до клубу «Стретфорд Таун» з Футбольного союзу Мідланд.
У липні 2010 року очолив молодіжну команду «Менсфілд Таун», проте через два місяці у клуба почалися фінансові проблеми й молодіжну команду було закрито. Незабаром після цього відновив кар'єру гравця, перейшовши до «Спелдінг Юнайтед». Дебютував за нову команду 2 жовтня 2010 року в програному (0:3) поєдинку проти «Таліпс». Після того як Данкан Расселл став помічником головного тренера «Менсфілд Таун» вирішив повернутися до команди й 19 листопада 2010 року уклав договір з командою. На той час у «Мансфілді» був переповнений травмованими гравцями лазарет, а в поєдинку проти «Кроулі Таун» на лаві запасних «городян» перебувало лише три гравці[11]. 30 березня 2011 року Голл потрапив до заявки на сезон. 7 червня 2011 року припинив виконувати функції помічника головного тренера.
Кар'єра в збірній
Незважаючи на те, що Голл народився в Англії, він мав ямайське коріння, тому на міжнародному рівні вирішив захищати кольори саме цієї збірної. Дебютував за «Реггі Бойс» у 1997 році, допоміг команді кваліфікуватися до фінальної частини чемпіонату світу 1998 року. На цьому турнірі виходив на заміну у всіх трьох поєдинках збірної Ямайки. Загалом же за збірну Ямайки відзначився 15-а голами в 41-у матчі.
Кар'єра тренера
Голл має тренерську ліцензію УЄФА категорії A. У 2009 році тренував футбольну команду коледжу Соліл. У листопаді 2010 року призначений помічником головного тренера клубу «Менсфілд Таун» з Футбольної Конференції.
Пол приєднався до Маркуса Лоу у клубі «Тамворт» з Національної ліги, де допомагав тренувати команду. Голл проживав у місцевості поблизу Тамворта, де ділився власним досвідом з молодіжним складом.
З 2015 року працює старшим тренером у відділі професіонального розвитку клубу «Квінз Парк Рейнджерс».
