Let's start by generalizing the notation a little ($d$ and $B$ will be positive integers):
- $H(P)$ will denote the height of a polynomial (maximum of absolute values of its coefficients).
- $S_d(B)$ will denote the set of polynomials $P(x)$ of degree $d$ with integer coefficients for which:
- $|P(k)|$ is prime for some positive integer $k$ but
- $|P(k)|$ is not prime for $0\leq k\leq B$.
- Finally, define $M_d(B)=\min\limits_{P\in S_d(B)} H(P)$
In this notation, the original question was asking for $M_5(10^6)$ and the simplified version is looking for $M_5(10^4)$.
Note that the definition of $M_d(B)$ relies on $S_d(B)$ being non-empty; a property that is not as obvious as it may seem (or I might have missed the easy proof of it). Since we are only going to focus on a few specific cases, we can overlook this as a technical detail.
Using computer-assisted search, I found the polynomial $$P_5(x)=39x^5 + 6x^4 + 21x^3 - 44x^2 + 47x + 15$$ which doesn't produce a prime until $x=13076$ and thus belongs to $S_5(10^4)$. This implies $M_5(10^4)\leq 47$. Note that the search was not exhaustive, so the bound is not necessarily the optimal one.
As expected, if we let the degree increase, the coefficients of the polynomial can be lowered: For example, another search found $$P_6(x)=25x^6 + 24x^5 + 11x^4 + 10x^3 + 25x^2 - 4x + 14$$ which is non-prime until $x=10905$, so $M_6(10^4)\leq 25$ (again, the search was non-exhaustive, thus the inequality).
On the other hand, going down to degree $4$ yields polynomial $$P_4(x)=11x^4 - 146x^3 - 99x^2 + 19x + 105$$ which isn't prime until $x=10774$. Thus, $M_4(10^4)\leq 146$.