I notice 48 PAYSON names in Canada under - http://www.canada411.comhttp://www.canada411.com -, of which about 5 are in NS - 3 in Clementsvale, Digby Co (telephone exchange is 467- Bear River) as well as a few in TRURO one hour north of Halifax, and the Halifax suburb of BEDFORD.
Most Canadian PAYSON names are mainly found in Ontario.
Here in Nova Scotia the nearest name to this one is PAYZANT, which may come from the French "paysan" or Italian "paisano" (both meaning "peasant" or "farmer") or some other source. When people were required to adopt a family name between 1250 and 1400, it is more than likely that many would have called themselves Paisano or Paysan, to describe their daily occupations. As you said in your posting, it is a very old name in Europe and was an early name in the New World.
You might want to call the few PAYSON people in NS and see what they know. NS Time is ONE HOUR LATER than U.S. Eastern or Ontario Time.