Henderson was born January 28, 1943, near Kincardine, Ontario. His mother, Evelyn, went into labour while staying at his father's parents' farm in the nearby community of Amberley during a snowstorm. She gave birth to Paul while the family was crossing Lake Huron via horse-drawn sleigh attempting to reach the hospital in Kincardine. His father, Garnet, was fighting for Canada during the Second World War at the time and did not meet his son until Paul was nearly three years old. Garnet worked for the Canadian National Railway following his return and the family – Paul was the eldest to brother Bruce and sisters Marilyn, Coralyn and Sandra – moved frequently to different posts in Ontario before settling in Lucknow.