$\newcommand{\De}{\Delta}
\newcommand{\ep}{\epsilon}
\newcommand{\R}{\mathbb{R}}$


Here is yet another answer providing the exact bound. This answer is perhaps a bit more elementary than the excellent answer given by user Algernon. Another advantage of this approach is that it produces the exact bound for any convex function $f$ in place of the function $p\mapsto p\ln p$.
 
To preserve the history of the question, I have also retained my previous answer, which used different (if somewhat similar) ideas and provided a suboptimal bound. 

Take indeed any convex function $f\colon[0,1]\to\R$ and consider the difference 
\begin{equation}
	\De:=\sum_1^N f(p_i)-\sum_1^N f(q_i)
\end{equation}
between the "generalized" entropies of $Q=(q_i)_{i=1}^N$ and $P=(p_i)_{i=1}^N$. 
We want to find the exact upper bound on $\De$ subject to the given conditions on $(P,Q)$. 
In what follows, $(P,Q)$ is a point satisfying these conditions. 
Without loss of generality (wlog), for some $k\in\{1,\dots,N\}$ we have $p_i\ge q_i$ for $i\le k$, $p_i\le q_i$ for $i\ge k+1$, and $q_1\ge\cdots\ge q_k$, so that 
\begin{equation}
	\ep=\sum_1^k(p_i-q_i)=\sum_{k+1}^N(q_i-p_i)>0. 
\end{equation}

Let $p_i^*:=q_i$ for $i=2,\dots,k$ and $p_1^*:=q_1+\ep[=\sum_1^k p_i-\sum_2^k q_i\le1]$. Then the vector $(p_1^*,\dots,p_k^*)$ [majorizes (in the Schur sense)][1] the vector $(p_1,\dots,p_k)$ and still satisfies the condition $p_i^*\ge q_i$ for $i\le k$. Also, since $f$ is convex, $\sum_1^k f(p_i)$ is Schur convex in $(p_1,\dots,p_k)$. So, wlog $(p_1,\dots,p_k)=(p_1^*,\dots,p_k^*)$. 

In particular, $p_1>q_1$ and $q_m\ge p_m$ for all $m=2,\dots,N$. 
Moreover, wlog $p_m=0$ for any $m=2,\dots,N$. Indeed, take any $m=2,\dots,N$ with $p_m>0$ and replace $p_1,q_1,p_m,q_m$ respectively by $p_1+t,q_1+t,p_m-t,q_m-t$, where $t:=p_m\in(0,1-p_1]$; then all the conditions on $P,Q$ will still hold. After this replacement, $\De$ will change by the sum of the nonnegative expressions $[f(p_1+t)-f(q_1+t)]-[f(p_1)-f(q_1)]$ and $[f(q_m)-f(p_m)]-[f(q_m-t)-f(p_m-t)]$; this nonnegativity follows by the convexity of $f$. Making such replacements for each $m=2,\dots,N$ with $p_m>0$, we will change $\De$ by a nonnegative amount, and will also get $p_m=0$ for all $m=2,\dots,N$ indeed. 

Thus, wlog 
\begin{gather}
	p_1=1=q_1+\ep,\quad p_i=0\ \forall i=2,\dots,N,\quad 
	\sum_2^N q_i=\ep. 
\end{gather}
Since $\sum_2^N f(q_i)$ is Schur convex in the $q_i$'s, wlog
\begin{align}
	\De=f(1)-f(q_1)-\sum_2^N f(q_i)  
	\le f(1)-f(1-\ep)-\ep f(\tfrac\ep{N-1})=:\De_{f;\ep,N}.   
\end{align}
The bound $\De_{f;\ep,N}$ on $\De$ is obviously exact, since it is attained when $p_1=1=q_1+\ep$ and $q_2=\cdots=q_N=\tfrac\ep{N-1}$. 

In the particular case when $f(p)=p\ln p$ (with $f(0)=0$), the exact bound $\De_{f;\ep,N}$ becomes $H(\ep)+\ep\ln(N-1)$, where $H(\ep):=\ep\ln\frac1\ep+(1-\ep)\ln\frac1{1-\ep}$. 

[1]: https://en.wikipedia.org/wiki/Majorization