My second comment indicates that I think you need to amend your conjecture, or else I don't understand.
Allow me to sketch some relevant ideas for getting non-trivial lower bounds. If my sketch does not suffice, I'll try to flesh it out when I have more time.
One should think of permutations here in terms of their cycle structures.
Your $q$ equations join some of the elements of ${\Bbb Z}/N{\Bbb Z}$ into cycles and others into finite order segments, each with, let's say, a head and a tail. Write $H$ for the set of heads, $T$ for the set of tails. Write $G$ for the graph of the partial function the equations determine.
Specifying a permutation satisfying the equations amounts to giving a bijection from $T$ to $H$. Since $|T|=|H|=N-q$, $(N-q)!$ permutations satisfy the equations and crucially, any given tail will have probability $1/(N-q)$ of joining any particular head.
The particular equations don't matter to your conjecture, only the resulting $T$ and $H$.
As per my comment, take $x_1=y_1=0$.
Now your probability conditions on either $(k_0,k_1)\in T\times H$ or $(k_0,k_1)\in G$.
Your probability calculation reduces to estimating the probabilities that either $(x_2+k_0,y_2+k_1)\in T\times H$ or $(x_2+k_0,y_2+k_1)\in G$.
That makes four cases to consider and I confess I have not yet worked out the details.
This helps with one case: given $T$, $H$ both of cardinality $N-q$, how small can we have the intersection $T\times H \cap ((T+x_2)\times (H+y_2))$. If $q$ is not too small,
the pigeon-hole principle gives a lower bound (but this does not exploit the product structure of $T\times H$).