Gradus and passus both have multiple meanings. Passus, as in its meaning related to feet, is also described as a unit of measurement, of five Roman feet. Gradus also has distinct meanings, including that on one which steps while ascending (as a stair), things resembling stairs, a march, a stage, a gait, a position, stand firm, of rank (in a hierarchy including of age), a degree of a circle, and even as a braid of hair.
However, both gradus and step are described, as a step, or a pace. What are the differences, if any, between the two, in describing steps or paces. It's possible that including differences as units of measurement may help in answering the question.
Dictionaries used were Smith's smaller Latin English Dictionary, Lewis and Short Dictionary, and Le Gaffiot (French). The reason for raising this question is as followup to this Stack Exchange Question about steps in mille passus. If no else includes them I will add as an answer the differences in Le Gaffiot to the definitions given in the English dictionaries.