Paulding war im Bahnradsport aktiv. 1985 gewann er den nationalen Titel im Scratch. 1986 konnte er diesen Titel verteidigen. 1984 wurde er Vize-Meister hinter Shaune Wallace. Den britischen Titel im 1000-Meter-Zeitfahren holte er 1989 und 1990. 1995 gewann er die Titel im Sprint und im Keirin. 1990 und 1992 wurde er beim Sieg von Stewart Brydon Vize-Meister im Sprint. 1989 siegte er im Cardiff Grand Prix Sprint. 1986 und 1990 startete er für Wales bei den Commonwealth Games im Bahnradsport. Er war mehrfacher Meister von Wales im Bahnradsport.
Paulding startete für die Vereine Cleveland Wheelers, City of Edinburgh Racing Club und VC St Raphael in Frankreich.