Fast evaluation of polynomials
I think you can find the pairs $(i,j)$ with $P_i(y_j)=0$ in time $N\cdot\log(N)$ for preprocessing and $k\cdot n\cdot\log(N)$ for processing, if you can use space $N$ for preprocessing the $y_i$:

Preprocessing consists of generating (1) the list $E$ of all $j$ such that $y_j$ is even, and (2) a tree (or something even faster) that you can query in time $\log(N)$ for a given $y$ to get the list of all $j$ such that $y=y_j$.

Now loop over all $x_i$, adding to the result either (1) all indices $(i, e)$ for $e\in E$ if $x_i$ is even or (2) all $(i, j)$ with $y_j = -x_i\cdot 2^l \bmod 2^k$ for some $l\le k$ (using the precomputed tree) if $x_i$ is odd.

The reason why this gives the correct result is written in my first comment to your question.