Your first two questions can be solved by an application of the reflection principle used to find a formula for the Catalan numbers; they're no more complicated than that.
(I'll slightly change your notation and always assume $k>0$ and just consider lines $y=x-k$ and $y=x+k$ to make the notation more intuitive. I'll also assume that $m,n,k$ are such that it's possible to get from $(0,0)$ to $(m,n)$ without crossing the line: $n \ge m-k$ in the first case and $n \le m+k$ in the second.)
For the first question: with no restrictions on where we walk, there are obviously $\binom{m+n}{m}$ paths from $(0,0)$ to $(m,n)$. We biject paths that touch $y=x-k-1$ with paths from $(0,0)$ to $(n+k+1,m-k-1)$ by the following rule: find the first point of the form $(x,x-k-1)$ on the path, and reflect all steps following that, switching $(+1,0)$ steps and $(0,+1)$ steps. Note that:
- A path $(0,0)$ to $(m,n)$ that goes through $(x,x-k-1)$ was later going to increase by $(m-x, n-x+k+1)$, but is now going to increase by $(n-x+k+1, m-x)$, so it ends up at $(n+k+1,m-k-1)$, and vice versa.
- We can always find a point of the form $(x,x-k-1)$ on a line from $(0,0)$ to $(n+k+1,m-k-1)$, because we assume $n \ge m-k$, so $m-k-1 < (n+k+1)-k$.
- Because we always choose the first point of the form $(x,x-k-1)$ on the path, this reflection is an involution (it is its own inverse) which confirms that it's a bijection.
So the number of "bad paths" is equal to the number of paths from $(0,0)$ to $(n+k+1,m-k-1)$, and the final answer is $\binom{m+n}{m} - \binom{m+n}{m-k-1}$.
We deal with the second question similarly, except that we reflect starting at a point of the form $(x,x+k+1)$ instead, turning paths that go to $(m,n)$ into paths that go to $(n-k-1,m+k+1)$, and getting a final answer of $\binom{m+n}{m} - \binom{m+n}{m+k+1}$.
The third question is trickier to deal with. If we're lucky, we have lines $y=x-k_1$ and $y=x+k_2$ that are sufficiently far apart that we can't cross one line, return to cross the other, and then come back to touch $(m,n)$. If that's the case, we can just subtract off both kinds of "bad paths" and get $\binom{m+n}{m} - \binom{m+n}{m-k_1-1} - \binom{m+n}{m+k_2+1}$ as our answer.
We can handle cases where we can "zigzag" and cross both lines at most once as follows: if we reflect around the first point that's past either line, then this bijects "bad paths" going past $y=x-k_1$ with paths to $(n+k_1+1,m-k_1-1)$ that don't go past $y=x+k_2$, which we can solve using the earlier method, and "bad paths" going past $y=x+k_2$ with paths to $(n-k_2-1,m+k_2+1)$ that don't go past $y=x-k_1$, which we can also solve using the earlier method. You can see how this gets complicated quickly.
On the other hand, if the two lines $y=x-k_1$ and $y=x+k_2$ are very close together, and $(m,n)$ is between then and very far from $(0,0)$, it might make sense to write a linear recurrence, as follows:
- Let $r_{i,j}$ be the number of paths between the lines that have $x-y=i$ when they reach the line $x+y=j$ (that is, after $j$ steps).
- We think of this as a one-term linear recurrence on the vector $$(r_{-k_2,j}, r_{-k_2+1,j}, \dots, r_{k_1,j}) \in \mathbb Z^{k_1+k_2+1}$$ because we can solve for the $j+1$ vector in terms of the $j$ vector.
- The final answer is $r_{m-n,m+n}$.
The characteristic polynomial of this recurrence has degree $k_1+k_2+1$, so the bigger this value, the worse the final answer.
