An inside forward, Paton began his senior playing career with Leeds United, returning to Scotland with Jock Stein's Dunfermline in 1961. He stayed ten years with the Fife side, helping them win the Scottish Cup in 1967-68 and reach the final in 1964-65. After over 200 first-team appearances he moved to Berwick Rangers in 1972, although the repercussions of two leg-breaks during his time with Dunfermline forced his early retiral after just five games for the Borderers.
Paton subsequently began a coaching career, initially assisting Bobby Seith at Hearts before becoming a manager in his own right at Raith Rovers in 1974. He left the Kirkcaldy side after one season and returned to supporting roles, most notably at St Johnstone, where he was Alex Totten's assistant when they were promoted to the Premier Division. He had previously aided Totten at Dumbarton.
In 1993, Paton was appointed manager of Dunfermline Athletic, helping the side earn promotion during his six-year tenure. He has since worked for his former assistant at Dunfermline Dick Campbell, when Campbell was manager of Brechin City.