The claim is true. Summary: we show by induction it is enough to prove
the congruence for $A_m$ for $m = 1,\ldots, k$ where $N+1 = p^k$,
and then we prove that by showing (in this particular case) that the
binomial coefficients are all divisible by $p^k$ (which doesn't hold in general).
Let
$$A_m = \sum_{j=0}^{m} \binom{Nm}{Nj}.$$
The claim to be proven is $A_m \equiv 2 \mod N+1$ if $N + 1 = p^k$ is a prime power.
Note that
$$(1 + x)^{Nm} = \sum_{j=0}^{Nm} \binom{Nm}{j} x^j,$$
if one lets $\zeta$ denote a primitive $N$th root of unity, then
$$ \sum_{i=0}^{N-1} (1 + \zeta^i)^{Nm} = \sum_{j=0}^{Nm} \binom{Nm}{j} \sum_{i=0}^{N-1} \zeta^{ji}$$
$$ = \sum_{j=0}^{Nm} \binom{Nm}{j} \begin{cases}
N, & j \equiv 0 \mod N \\
0, & j \not\equiv 0 \mod N. \end{cases}$$
$$ = N \sum_{j=0}^{m} \binom{Nm}{Nj}.$$
So if, for $m \ge 1$,
$$B_m = \sum_{i=0}^{N-1} (1 + \zeta^i)^{Nm} = \sum_{\zeta^i \ne -1} (1 + \zeta^i)^{Nm},$$
then the congruence $A_m \equiv 2 \mod (N+1)$ is equivalent to the congruence $B_m \equiv - 2 \mod (N+1)$.
The roots of unity are all distinct modulo $p$, so there is a unique $\zeta^i \equiv -1 \mod p$. If $p$ is odd, then $N$ is even, and it is $\zeta^{i} = -1$, and $(1 + \zeta^i) = 0$. If $p = 2$, then $N$ is odd, and it is $\zeta^i = 1$ and $(1 + \zeta^i) = 2$. In the latter case, for $m \ge 1$, the term $(1 + \zeta^i)^N$ is equal to $2^N$ which is certainly trivial modulo $2^k = N+1$ because $2^N \ge N+1 = 2^k$.
Hence we have
$$B_m = \sum_{\zeta^i \ne -1} (1 + \zeta^i)^{Nm} \equiv \sum_{\zeta^i \not\equiv -1} (1 + \zeta^i)^{Nm} \mod p^k.$$
The polynomial $X^N - 1$ is separable over $\mathbf{F}_p$.
Moreover, its roots over this field are precisely the units of $\mathbf{F}_q$, since the
units in that field are cyclic of order $q - 1 = N$.
Hence the extension cut
out by the roots of unity $\zeta^i$ over $\mathbf{Q}_p$ is just the fraction field of the Witt
vectors $W(\mathbf{F}_q)$. All of this is just to say (if you don't know algebraic
number theory) that it makes sense to talk of congruences for these algebraic
integers modulo powers of $p$, and that we also have (assuming $\zeta^i \not\equiv -1 \mod p$):
$$(1 + \zeta^i)^N \equiv 1 \mod p$$
Hence it also follows that
$$((1 + \zeta^i)^{N} - 1)^k \equiv 0 \mod p^k$$
But then, for any non-negative integer $r$, we have:
$$\sum_{\zeta^i \not\equiv -1} ((1 + \zeta^i)^{N} - 1)^k (1 + \zeta^i)^{Nr} \equiv 0 \mod p^k,$$
or, expanding out:
$$ \sum_{r=0}^{k} B_{n+ r} (-1)^r \binom{k}{r} \equiv 0 \mod p^k,$$
and thus we obtain the $k$-term recurrence
$$B_{n+k} (-1)^{k-1} = \sum_{r=0}^{k-1} B_{n+r} (-1)^r \binom{k}{r} \mod p^k$$
Suppose that $B_m \equiv -2 \mod p^k$ for $m = 1, \ldots, k$.
Then, by induction, we get $B_m \equiv -2 \mod p^k$ for all $m$, simply
by applying the recurrence above and using the identity
$$\sum (-1)^r \binom{k}{r} = 0.$$
So we just need to prove the first few values of $A_m \equiv 2 \mod p^k$.
But now we can look at the actual binomial coefficients themselves.
Suppose that $N+1 = p^k$. We claim that, in the range $a+b \le k$ and $a,b > 0$, we have
$$\binom{N(a+b)}{Nb} \equiv 0 \mod p^k.$$
Once we know this, it follows that $A_m \equiv 2 \mod p^k$
for $m \le k$ and we are done by induction.
In fact, since trivially $k \le p^k$, we are done by the following stronger claim.
Claim
Suppose that $a + b \le p^k$ and $N + 1 = p^k$. Then the $p$-adic valuation of
$$\binom{N(a+b)}{Nb}$$
for $a,b \ge 1$ is exactly $k$.
Proof
The $p$-adic valuation of the binomial coefficient is precisely
the number of times one has to carry the one when adding $Na$ and $Nb$.
For a number $0 \le m-1 < p^k$ (which includes $a-1$, $b-1$, and $c = a+b-1$, we may
write
$$m - 1 = (m_{k-1}, m_{k-2}, \ldots, m_0)$$
in base $p$, and we may also write
$$p^k - m = (p^k - 1) - (m - 1) = (m'_{k-1}, m'_{k-2}, \ldots, m'_0).$$
Since
$$m-1 + (p^k - m) = p^k - 1,$$
we have, for all $i = 0,1,\ldots,k-1$, that
$$m_i + m'_i = p - 1.$$
We now find that $aN$, $bN$, and $cN$ have $p$-adic expansions as follows
$$aN = (a_{k-1}, a_{k-2}, \ldots, a_0,a'_{k-1}, \ldots, a'_0),$$
$$bN = (b_{k-1}, b_{k-2}, \ldots, b_0,b'_{k-1}, \ldots, b'_0),$$
$$cN = (c_{k-1}, c_{k-2}, \ldots, c_0,c'_{k-1}, \ldots, c'_0),$$
As noted before, we have
$$a_i + a'_i = p-1, \ b_i + b'_i = p-1, c_i + c'_i = p -1.$$
Hence
$$(a_i + b_i) + (a'_i + b'_i) = (c_i + c'_i) + p - 1,$$
or
$$(a_i + b_i - c_i) + (a'_i + b'_i - c'_i) = p - 1.$$
Now
$$a_i + b_i = c_i +
\begin{cases} p & \text{carry required} \\
0 & \text{no carry required}\end{cases} \
+ \begin{cases} -1 & \text{carry required in $i-1$ slot} \\
0 & \text{no carry required in $i-1$ slot} \end{cases}$$
and the same with $a'_i$, $b'_i$, and $c'_i$.
There is a unique way of writing $p-1$ as a sum of exactly two terms in the set $\{p,0,-1,0\}$.
It follows that in the pair of slots $(i,i+k)$, either exactly one of
the pairs coming from the $m_i$-coefficient and the $m'_i$ coefficient requires "carrying the one,"
(It also follows that exactly one of the pairs $m_{i-1}$ and $m'_{i-1}$ (which might be $m'_k$ if $i = 0$) also requires carrying the one, although this is the same statement for $i-1$ instead of $i$. This is why the sum is $p-1$ and not $p$.)
But since exactly one of the pair coming
from the $m_i$-coefficient and the $m'_i$ coefficient requires "carrying the one,"
exactly half the terms have this property,
and we are done.
Additional: A weaker version of the induction argument is as follows.
By the analog of Fermat's Little Theorem and Euler's Theorem in $W(\mathbf{F}_q)$ ($q = p^k$), one has the identity
$$\gamma^{N p^{k-1}} = \gamma^{(q-1)p^{k-1}} \equiv 1 \mod p^k$$
for any $\gamma \in W(\mathbf{F}_q)^{\times}$, that is, any $\gamma \not\equiv 0 \mod p$. It follows that
$$\begin{aligned}
B_{m + p^{k-1}} = & \ \sum_{\zeta^i \not\equiv - 1} (1 + \zeta^i)^{mN + N p^{k-1}}\\
\equiv & \ \sum_{\zeta^i \not\equiv - 1} (1 + \zeta^i)^{mN} \mod p^k\\
= & \ B_m \mod p^k, \end{aligned}$$
and so by induction it suffices to show that $B_m \equiv -2 \mod p^k$ for $m = 1, \ldots, p^{k-1}$ rather than $m = 1, \ldots, k$. Since the second step actually proves the congruence $B_m \equiv -2 \mod p^k$ for $m = 1, \ldots, p^k$, this also suffices, and one might find this version of the inductive step slightly easier.
Best Answer
Well, for starters, for what value of $k$ is $f(n,k)=\frac1{k!}\binom{n-1}{k-1}$ maximized? Consider the ratio $$ \frac{p(n,k+1)}{p(n,k)}=\frac{n-k}{k(k+1)} $$ This ratio starts above one when $k$ is small, and ends below one when $k$ is close to $n$. The time when the ratio goes from above one to below one is where $p(n,k)$ is maximized. We can see this occurs at about $k\approx -1+\sqrt[]{n+1}$, suggesting that plugging in $\sqrt{n}$ for $k$ into that inequality should give the best bound on $p(n)$. In other words, you should use $$ p(n)\ge \frac1{(\sqrt{n})!}\binom{n-1}{\sqrt n-1} $$ and show the right hand side to be grows faster than $e^{c\sqrt{n}}$. To do this, use Stirling's approximation.
The product of $\pi(n)$ distinct numbers positive integers is at least $\pi(n)$!. Since you know the product of the $\pi(n)$ primes in $[1,n]$ is at most $4^n$, this tells you $$ \pi(n)!\le 4^n $$ If $\pi(n)$ was not $O(n/\log n)$, then it follow that $\pi(n)=C(n)n/\log n$, where $C(n)$ is some function which is not bounded, meaning $C(n)$ can be made arbitrarily large by plugging in an appropriate $n$. So show that $$ (C(n)n/\log n)!\le 4^n $$ leads to a contradiction for such a function $C(n)$. Again, Stirling's approximation is indispensable.