We give a quite formal, and unpleasantly lengthy, argument. Then in a remark we say what's really going on. Let $n$ be an integer. First note that there are integers $x$ such that $n-xd\ge 0$. This is obvious if $n\ge 0$. And if $n \lt 0$, we can for example use $x=-n+1$.
Let $S$ be the set of all non-negative integers of the shape $n-xd$. Then $S$ is, as we observed, non-empty. So there is a smallest non-negative integer in $S$. Call this number $r$. (The fact that any non-empty set of non-negative integers has a smallest element is a hugely important fact equivalent to the principle of mathematical induction. It is often called the Least Number Principle.)
Since $r\in S$, we have $r\ge 0$. Moreover, by the definition of $S$ there is an integer $y$ such that $r=n-yd$, or equivalently $n=yd+r$.
Note that $r\lt d$. For suppose to the contrary that $r \ge d$. Then $r-d\ge 0$. But $r-d=r-(y+1)d$, and therefore $r-d$ is an element of $S$, contradicting the fact that $r$ is the smallest element of $r$.
To sum up, we have shown that there is an $r$ such that $0\le r\lt d$ and such that there exists a $y$ such that $r=n-yd$, or equivalently $n=yd+r$.
Case (i): Suppose that $r\lt \dfrac{d}{2}$. Then let $k=y$ and $\ell=r$. We have then $n=kd+\ell$ and $0\le \ell\lt \dfrac{d}{2}$.
Case (ii): Suppose that $r \ge \frac{d}{2}$. Since $d$ is odd, we have $r\gt \dfrac{d}{2}$. We have $\frac{d}{2}\lt r \lt d.$ Subtract $d$ from both sides of these inequalities. We obtain $-\dfrac{d}{2}\lt r-d\lt 0,$ which shows that $-\frac{d}{2}\lt n-yd-d\lt 0.$ Finally, in this case let $k=y+1$ and $\ell=n-kd$. Then $n=kd+\ell$ and $-\dfrac{d}{2}\lt kd+\ell\lt 0.$
Remark: There is surprisingly little going on here. We first found the remainder $r$ when $n$ is divided by $d$. But the problem asks for a "remainder" which is not necessarily, like the usual remainder, between $0$ and $d-1$. We want to allow negative "remainders" that are as small in absolute value as possible. The idea is that if the ordinary remainder is between $0$ and $d/2$, we are happy with it, but if the ordinary remainder is between $d/2$ and $d-1$, we increase the "quotient" by $1$, thereby decreasing the remainder by $d$, and putting it in the right range. So for example if $n=68$ and $d=13$, we use $k=5$, and $\ell=3$. If $n=74$ and $d=13$, we have the usual $74=(5)(13)+9$. Increase the quotient to $6$. We get $74=(6)(13)+(-4)$, and use $k=6$, and $\ell=-4$.
We gave a proof in the traditional style, but the argument can be rewritten as an ordinary induction argument on $|n|$. It is a good idea to work separately with non-negative and negative integers $n$. We sketch the argument for non-negative $n$. The result is obvious for $n=0$, with $k_0=\ell_0=0$. Suppose that for a given non-negative $n$ we have $n=k_nd+\ell_n$, where $\ell_n$ obeys the inequalities of the problem, that is, $-d/2\lt \ell_n\lt d/2$. If $\ell_n\le (d-3)/2$, then $n+1=k_{n+1} +\ell_{n+1}$, where $k_{n+1}=k_n$ and $\ell_{n+1}=\ell_n+1$. If $\ell_n=(d-1)/2$, let $k_{n+1}=k_n+1$ and $\ell_{n+1}=-(d-1)/2$. It is not hard to verify that these values of $\ell_{n+1}$ are in the right range.