As the comments have already indicated, there is an $O(n^2)$ algorithm for finding such labelings without the restriction on $k$: see arXiv:0705.1025. And the labeling, if it exists, is essentially unique, so once you have computed it you can easily test if it uses $k$ or fewer bits.

But reinterpreting your question as asking whether there's a *more* efficient algorithm when $k$ is a small parameter (it can't be constant, but it could be as small as logarithmic): the answer is yes and no. You can find each bit of a valid labeling (when a labeling exists) by a breadth first search (see the same paper), so you can find the whole labeling in time $O(k(n+m))$ where $n$ and $m$ are the number of vertices and edges in the input. And I'm pretty sure the same bit-parallel technique for doing multiple BFS's at once that I used in the paper will work again in this case and reduce the time to $O(kn+m)$. That may be significantly less than $n^2$, especially because $m$ is always $O(n\log n)$ in graphs that can be labeled in this way. But, I don't know of a way to test whether the result is actually a valid labeling, any faster than $O(n^2)$.

isometric". – Ben Barber Nov 27 '13 at 16:06