Proving that Turing Machine M runs in time $O(2^{dn})$
Your intuition is problematic, for the following reason: you are given a specific machine $M$, not a language. Therefore, if you describe an algorithm that runs in $O(2^{dn})$ and decides the same language, you effectively prove that $L(M)$ is decidable in $O(2^{dn})$, but that does not imply that $M$ itself runs in that time frame.

As the hint suggests, consider the number of possible configurations of $M$: recall that a configuration of a TM consists of the contents of the tape, the position of the head, and the state. Given that the alphabet of the machine is fixed, and that the tape used in the run of $M$ on $x$ is of size $c\cdot |x|$, try to bound the number of possible configurations (expressed in the size of $M$ and $|x|$)

Now, recall that $M$ always halts. What does that mean about the sequence of configurations it goes through in its run on $x$? 

Combining these two observations you will get the answer. Comment if you need more hints.