Opinions differ here: personally, I've never considered it odd. When every Tom, Dick, and Harry is named William, so to speak, you may need something to distinguish them, perhaps for record-keeping if nothing else. So append a word that's unique or less common in the area of interest, and a reasonable source of such a word is a description of the person.

There is a wide variety of descriptions in English: "son of [male name]" (or just "[male name]" or "[grammatical possessive of male name]" where the "son of" is implied), a descriptive nickname (Broadhead, Chaffin 'bald', Thoroughgood, Daft, Careless, Pennyfather 'miser'), a general toponym (Atwood, Bythewood) or locative (de Lincoln). Why not occupation as well, since few men are notable as smiths or fullers or shoe-makers (Chaucer) or dyers (Lister), and therefore it could serve just as well to uniquely identify someone, or at least cut down on the possibilities as much as "Tall" does?

Indeed, you provide an excellent example: "My dad, for example, decided to call one of the Ednas in our extended family Edna Nurse in order to distinguish between them." Why would Nurse be improbable when Black (for black hair) or Sleight ('cunning') or York (place-name) or atte Lee (generic place-name) are not? They could all be characteristics that X has that Y, Z, and W do not.

EDIT: You wrote "Was it for branding purposes, where the title of your business was John Smith?" That supposes that the occupational byname was chosen by the bearer. Note that in your example, the nickname was given by someone else. Since it was third-party clerks in many cases identifying other people in legal records, I think it's entirely possible that it was the clerks who chose the surnames.

As for "why": in general, we'll never know. Certainly Pope and Legate, while appearing like occupational names, are highly unlikely to have ever had a pope or legate in their near ancestry. Even Priest: each parish was supposed have its priest or priest-substitute, so you didn't need to advertise to undercut another priest. Certainly at least some surnames were chosen by other people, unless Roger Fuckebythenavele in 1310 had a uniquely self-deprecating sense of humor, and given Norse attitudes towards homosexuality, I think it unlikely that Ásmundr kastanrazi ('wiggle-arse') chose his own nickname.

Reaney, in the introduction to A Dictionary of English Surnames, p. xliii, has an amusing paragraph about pupils' and teachers' nicknames and their origins from his schooldays. After discussing guys named 'Feet', 'Bublum Squeaks', 'Joe Plug', 'Wally' and 'Mike' (neither related to their given or surnames), and 'Polly', he ends,

'Kip' had an interesting history. Originally 'Skipper' -- Why, nobody knew -- it quickly became 'Kipper', later shortened to 'Kip'. It is not surprising, therefore, if we frequently fail to get behind the mentality of the thirteenth and fourteenth centuries and cannot interpret their nicknames.

TL;DR: why not? They're as good as any.