Is there a distinction between 我们决定早动身 and 我们决定早些出发 which mean "we decided on an early start"?
Both 出发 and 动身 means "depart/ move out"


出发 literally means 'launch out' . It is more colloquial
动身 literally means 'move oneself' . It is more literary



  动身 emphasizes on the action of 'moving oneself from his current location' (imply starting a journey to a destination)


Example: 


动身去北京 (depart for the journey to Beijing)



  出发 emphasizes on the action of 'moving out' .  You can 出发 to a journey or 出发 to fulfill a mission


Example: 


出发去北京 (depart for the journey to Beijing)
出发去打仗 (off to fight a war)
出发去打猎 (off to hunting)



  We don't say '动身去打仗' or '动身去打猎'


~


  我们决定早动身 and 我们决定早些出发 which mean “we decided on an early start”?


Both mean "we decided to depart early."  The difference between 动身 and 出发 is stated above.

If you meant "off to a hunting trip", "off to fight a battle" or " depart for a sight seeing tour" , you can only use '出发'. If you meant "depart for a journey",  then either would be suitable.