Striker Mark Paul joined Southampton in July 1998 from King's Lynn for £75000 but which could rise to £100,000 or more dependent on appearances. The 19 year old striker had a trial with Norwich when he was 16 but opted to join Peterborough instead. A fractured ankle saw him quit The Posh and drift away from the professional game. Impressive performances in the Peterborough Sunday league saw him approached by Eastern Counties league side Warboys Town for whom he signed. His speed and finishing quickly drew the attentions of other clubs and he joined King's Lynn for £2000.

Even then he was monitored by league clubs including Norwich and West Ham. Mark's former King's Lynn manager Peter Morris (then at Kettering) claimed that West Ham offered £50,000 for Mark months before his signing for Southampton. Morris also claimed that Manchester United's Alex Ferguson rang to enquire about the youngster whilst Spurs and Derby were also interested. However the Lynn chairman John Scales claimed that the only firm bid was from Port Vale at £20000. Former Warboys manager Robbie Cooke described Paul as "an untapped Michael Owen because of the way he finishes and the fact that he's very quick and very direct.

At the Dell, Mark would have the opportunity to develop into an effective striker alongside old hands such as Mark Hughes, Stuart Ripley and Matt Le Tissier. Although Mark managed to sit on the bench for a few games, he wasn't able to claim a regular spot in the Saints' first team. In July 1999, it was reported that Mark had joined Hull City. In fact, he had been training with the Tigers but had also been approached by Peterborough. Stoke and Carlisle were also showing interest according to Sport First (25th July 1999) but Mark hadn't accepted any offers due to being injured.

Teletext reported on 14th September 1999 that Mark had joined Peterborough on trial. This did not materialise into anything permanent and in January 2000, Mark rejoined former Lynn manager Peter Morris who was managing Conference side Kettering Town. In September 2000, Mark joined Bedford of the Ryman League. He remained there until March 2003 when he was released.

Despite reports that Mark had signed for Aylesbury, he in fact returned to Peterborough to join their leading non-league side Yaxley. After scoring seven goals in seven games for Yaxley, Mark was re-signed by King's Lynn in the last days of March 2003. He made his debut at Bashley on March 29th 2003, coming on as a substitute and scoring in a 2-1 Linnets victory. Mark however was freed by the Linnets in the 2003 pre-season following the signing of Malcolm Ndekwe from rivals Stamford. In mid June 2003, Mark signed for fellow Dr Martens league side Grantham Town.

At the end of August 2003, Mark signed for Cambridge City on non-contract terms along with former Stevenage player Leon Bell. Two thirds of the way into the following month saw Mark depart again - this time to join Stamford. In February 2004, Mark rejoined Yaxley but left them for Wisbech, debuting for them on Valentines Day.

At the start of the 2004/5 season, Mark was again playing for Yaxley. He was linked with a return to Stamford in June 2006 but chose to remaiin at Yaxley.

Mark joined Ely City in February 2008 but returned to Yaxley at the end of the season. He wasn't there long as he was one of five Yaxley players to swap UCL Premier Division football at Yaxley for a UCL Division One title tilt with Peterborough Northern Star in early June 2008. The others were wideman Ian Edge, midfielders Lee Blewitt and Scott Bogusz, and defender Anthony Thomas

Mark moved on to Deeping Rangers in June 2009