Thanks, Jeremy and Andreas, for your comments. In the notes by Ackerman (http://www.math.upenn.edu/~nate/papers/paper_3/paper_3.pdf) already the first paragraph has the clue:
[...] the distance function takes values in a fixed complete lattice (and not necessarily in the reals). What I had not imagined when asking my question was that people would speak of a "distance function" in such a case at all, and not at least for instance of a "generalized distance function"; considering that http://en.wikipedia.org/wiki/Distance_function (which redirects to [[Metric space]]) and even http://en.wikipedia.org/wiki/Distance#General_case specificly require that any distance function should take values in the reals.
(Or could you perhaps suggest another online reference for terminology than Wikipedia?)
So a generalization of the notion "distance function" (perhaps even the essental essential generalization) is apparently achieved by generalizing its codomain from the reals,
[... the triple](cmp. Definition 1.1 of Ackerman's paper).
$(\Gamma, \leq, 0)$[which is] a complete lattice with minimal element 0
There's an additional point to my question, though, which I now can try to express more specificly -- perhaps:
What exactly is required to induce a partial order "
$\leq$" in a given set
I suppose: some particular relation (or collection of relations) to some other, already given partially ordered set(s); i.e. something that may well be called an "encoding" (although I don't know if that's a precise, technical term, of course ...)
p.s. There are only 600 characters available for a comment?!? And it can't even be formatted sensibly? ... Sorry -- then I rather reply by posting an "Answer" than trying to "comment".