Consider a random walk starting at a positive integer $k$. Now, trying to calculate the probability of returning to zero (from $k$), I did the following:
\begin{align} P&(\text{returning to zero}) \\ &=P(\text{returning to zero in } k\text{ steps}) \\ &\quad+ P(\text{returning to zero in } k+2\text{ steps} ) \\ &\quad+ P(\text{returning to zero in } k+4\text{ steps} ) \\ &\quad+\cdots \\ &=\Bigl({1\over 2}\Bigr)^k \\ &\quad+\Bigl({1\over 2}\Bigr)^{k+2}{k+2\choose 2} \\ &\quad+\Bigl({1\over 2}\Bigr)^{k+4}{k+4\choose 4} \\ &\quad+\cdots \\ &=\Bigl({1\over 2}\Bigr)^k\sum_{j=0}^\infty\Bigl({1\over 2}\Bigr)^{2j}{k+2j\choose 2j} \end{align}
Now as I put some numbers in Desmos, it is very clear that this evaluates to greater than $1$. Clearly, I’ve made some mistake.
Your first mistake is that the number of ways to walk from $k$ to $0$ in $k+2j$ steps should be $\binom{k+2j}j$, not $\binom{k+2j}{2j}$.
Furthermore, in order to have the probabilities of the events sum to $1$, the events need to be disjoint, so the event where you return to $0$ in $k+2j$ steps must be exclude returning to $0$ at any previous time. You want to find the probability of returning to $0$ for the first time in $k+2j$ steps.
In order to return to $0$ for the first time in $k+2j$ steps, you need to move from $k$ to $1$ in $k+2j-1$ steps without reaching $0$, then step down. To calculate the number of ways to do this, you need to use a clever trick called the reflection principle.
Here's how the reflection principle works. Let us instead count the "bad" paths from $k$ to $1$ with a length of $k+2j-1$ which do reach $0$ at some point. If you take such a bad path, and negate each of its steps after the first point it reaches $0$, then it turns out you get a path from $k$ to $-1$ with a length of $k+2j-1$. Furthermore, this process is reversible; given any path from $k$ to $-1$ with a length of $k+2j-1$, if you negate each of the steps after the first time the path reaches $0$ (which must exist), then you get a "bad" path from $k$ to $0$. Therefore, the number of bad paths is just the number of paths from $k$ to $-1$, which is $$ \binom{k+2j-1}{j-1} $$ Therefore, the number of good paths is the total number of paths from $k$ to $1$ minus the number of bad paths, so $$ \binom{k+2j-1}{j} - \binom{k+2j-1}{j-1}=\frac{k}{k+j}\binom{k+2j-1}{j} $$ Finally, we multiply the number of paths by the probability $(1/2)^{k+2j-1}$ of each path occurring, times an extra $1/2$ to account for the final down step to move from $1$ to $0$. The result is $$ P(\text{reaching $0$ for first time in $k+2j$ steps})=\left(\frac12\right)^{k+2j}\cdot\frac{k}{k+j}\binom{k+2j-1}{j} $$ You can check that this series converges, though you will find it converges quite slowly (the sum of the first million terms is $\approx 0.998307$).