He was signed by Middlesbrough straight after he left school. With his chances of first team football at the Riverside Stadium very scarce, he went on loan to Gateshead, Hartlepool United for a month and then to Stoke where he made 3 appearances. After Middlesbrough released him, Stoke did not hesitate to sign him permanently. Whilst at Stoke he went on loan to Cambridge United where he scored 5 goals in 14 games. After his time at Stoke he moved to Rochdale, who paid a club record fee of £150,000 to bring him to Spotland Stadium. He was an immediate success taking Rochdale to the brink of the play-offs with his goals before an unfortunately-timed injury. This prevented him from playing more than a marginal role the following season when Dale did make the play-offs. He managed to shake off the injury for the 2002–03 season when he played a key role in Dale's run to the Fifth Round of the FA Cup. With the end of his contract looming Connor was sold just before transfer deadline day in March 2004 for just £35,000 to Swansea City despite Dale's precarious League position. Connor proved to be a hardworking, skilful striker, forging effective partnerships with both Lee Trundle and Kevin Nugent. Often maligned for basically not being Trundle, Paul scored a number of very important goals with some excellent finishes. The second top goal scorer in the 2004–05 season with 12 finishes in 44 appearances was 3 or 4 better than their top scorers totals for a number of seasons during the 1990s. In January 2006, he had fallen down the pecking order at the Liberty Stadium, and so the Leyton Orient manager, Martin Ling, signed him for £40,000. He made 34 appearances, scoring 7 goals.
On 15 January 2007 he signed for Cheltenham Town for an initial fee £20,000 with a further £5,000 payable if the Robins avoided relegation from League One that season. He met up with his new teammates for the first time just two hours before making his debut in the 1–1 home draw with Scunthorpe United on 16 January 2007 before netting his first goal for the club in the 2–1 home victory over his former club Swansea City on 3 February 2007. Having helped the club avoid relegation, Connor was rewarded by being allocated the number 9 shirt for the 2007–2008 season: the first time he had been given a squad number lower than 16. However, his preparations for the season were disrupted as he was forced to miss most of the preparation with an ankle injury suffered during pre-season training in Germany. Despite a number of hard working performances, Connor found the goals hard to come by and went almost eleven months between his first and second league goals for the club; the second coming in the 1–0 home victory over Port Vale on 2 January 2008 and he managed just four league goals from 26 starts and a further 13 substitute appearances that season. He again struggled on the goalscoring front in the 2008–2009 season and in January 2009, Connor was made available for transfer by Town manager Martin Allen but he forced his way back into the club's starting eleven towards the end of the season. Having scored just two league goals all season, he was released by the club at the end of the season with manager Martin Allen commenting that "at this present moment in time we cannot offer him a new deal. I have also informed him that the door is still open but I have to manage my budget very carefully and have to look at other options before we can offer him a new deal".
Connor commenced the 2009–2010 season by training with Cheltenham Town before joining Lincoln City on trial. He agreed a one-year contract with the Sincil Bank based club on 21 July 2009. He debuted for the club in the 1–0 home victory over Barnet on 8 August 2009 but a thigh strain picked up in training saw him miss half of the August fixtures whilst a knee injury sustained in the 3–0 home victory over Darlington on 5 September 2009 kept him on the sidelines for almost five months before returning to the first team squad for the game with Bradford City on 23 January 2010 for which he was an unused substitute. He then struggled to make the starting eleven, starting only five games in the remainder of the season and he departed Sincil Bank on 5 May 2010 with his contract cancelled by mutual consent.
On 28 July 2010 he joined Mansfield Town on a one-year contract with the club's supporters group The 12th Stag making a contribution to his wages. Connor made an immediate impact scoring two goals on his debut.
On 1 December 2011, Connor joined Gainsborough Trinity on a part-time basis; a move designed to allow him to explore other alternatives after football whilst also spending more time with his young family. In June 2017 he was appointed player-coach at West Auckland Town.
