Paille started out with Sochaux, with whom he played for 7 seasons between 1982 and 1989. He helped the Montbéliard side reach the 1987–88 Coupe de France final, and was voted French Player of the Year at that season's end. He also earned his eight caps for France between 1986 and 1989, scoring a single goal for les Bleus.
The rest of Paille's playing career was somewhat nomadic: after leaving Sochaux for Montpellier HSC in 1989, whom he joined with close friend Eric Cantona, he spent no more than 2 seasons at the same club during the next 9 years. He joined Girondins de Bordeaux in December 1989, then FC Porto in the summer of 1990. Following a two-year spell at SM Caen between 1991 and 1993, he returned to Bordeaux for a single season. In 1994 he joined Olympique Lyonnais, then moved to Swiss side Servette Geneva in 1995. After one season he returned to France with FC Mulhouse. In September 1995 Paille retired after failing a drugs test due to cannabis use. He told L'Equipe this was due to serious personal problems. He joined Scottish side Heart of Midlothian in 1996. He was released by the Edinburgh club in May 1997 after failing a drugs test due to his use of Dinintel.
Paille then returned to first club Sochaux, where he held a coaching position for three years between 1999 and 2002. He gained his first executive role when he was appointed head coach of Besançon RC but left in 2004. He was briefly head coach at Racing Club Paris in 2005, before being approached by Angers in May 2005. He left the Blanc et Noir in June 2006.