K-trees can be defined by an iterative construction process where in every step a "new" vertex is added adjacent to some k mutually adjacent "old" vertices. Such a process may be represented by the recursive labeling in which the consecutive integers are associated with the vertices of a k-tree as they are added in the construction. Other, more visually appealing structures representing a particular construction process are the marked tree and the spatial tree. Nodes of these trees correspond to (k+1)-cliques of the k-tree. Using the notion of a cable of k vertex-disjoint paths between two vertices of a k-tree, we define the k-cable distance. We discuss the values of the shortest-path and the k-cable distances between vertices of a k-tree and present algorithms to compute them in terms of the different representations of k-trees.