You know that if you have a point charge with charge $Q$, then the potential difference $V$ between spatial infinity and any point a distance $r$ from the charge is given by $$V_\textrm{point}=\frac{kQ}{r}.$$ You also know that the electric field from an infinite sheet of charge with charge density $\sigma$ is given by $$E_\textrm{sheet}=2 \pi k \sigma. $$
Because the electric field is uniform, you correctly concluded that there must be an infinite potential difference between any point and spatial infinity. You are surprised because this seems at odds with the first formula for $V_\textrm{point}$.
However, there is a good explanation. If $\dfrac{kQ}{r}$ is originally for a point charge, what values of $Q$ and $r$ should we plug in for the case of a sheet? Well, notice that the sheet has an infinite amount of charge, so that perhaps $Q$ should be infinite. This explains why we might get an infinite potential difference. However, there is a competing effect occuring with $r$. As you go farther out on the infinite sheet, you get farther and farther away from the point where you are trying to compute the potential, so it seems like maybe $r$ should be very big, maybe infinitely big as well. Let's see how to do the problem correctly.
To do the problem correctly, you need to realize that each point on the infinite sheet acts like a little point charge, so each point gives its own $\dfrac{kQ}{r}$ contribution. The total potential, by superposition, is the sum of these contributions. We can sum up the contributions by integration. Let's first pick a coordinate system where the plate is on the $x$-$y$ plane, and the point where we want to know the potential is on the $z$ axis. We can switch to cylindrical coordinates where $\rho = \sqrt{x^2+y^2}$. Then the distance $r$ between the point with coordinate $z$ on the $z$ axis and a point with coordinate $\rho$ is given by $r = \sqrt{z^2 + \rho^2}$, and so, applying the $kQ/r$ formula, the contribution $dV$ to the potential from a bit of charge $dQ$ a distance $\rho$ from the origin is given by $$dV = \frac{kdQ}{\sqrt{z^2+\rho^2}}.$$ Integrating this over all $\rho$ we find
$\begin{equation}
\begin{aligned}
V&=\int^\infty_0 \frac{2 \pi k \sigma \rho d \rho}{\sqrt{z^2+\rho^2}} \\
&= \pi k \sigma \int^\infty_0 \frac{du}{\sqrt{z^2+u}}\\
&=2 \pi k \sigma \left( \sqrt{\infty + z^2} - |z| \right).
\end{aligned}
\end{equation}$
Because of the infinity in the square root, the potential above is in fact infinite, even though were started with a finite $kQ/r$ law. This infinity was possible because we had infinitely much $Q$. Notice the electric field still works out because the infinite part does not have a spatial gradient: $$E=-\dfrac{dV}{dz} = -2 \pi k \sigma \left( \dfrac{z}{\infty + z^2} - 1\right) \hat{z} = 2 \pi k \sigma \hat{z}.$$
When dealing with infinitely long line charges (basically a cylindrical geometry) calculating the potential relative to infinity becomes a problem. You have to establish a reference (ground/earth) at a finite location. So, your result of an infinite potential difference is not incorrect, although it is confusing the first time you see it.
This site provides a description of why this happens. You are effectively grounding one end of your distribution, then stacking an infinite amount of charge down the line.
Best Answer
The use of the formula $\displaystyle V(r) - V(\infty) = -\int^r_{\infty} \vec{E}\cdot d\vec{\ell}$ requires a little care.
If there is an electric field $\vec E$ then the force on unit positive charge due to this electric field is $\vec E$.
The work done by the electric field in moving this charge $d \vec r$ is $\vec E \cdot d\vec r$ and the work done by an external force is $\left(- \vec E \right) \cdot d\vec r$.
There are two equivalent ways to define the potential at a point.
The first definition is that the potential at a point is minus the work done by the electric field in taking unit positive charge from infinity to the point.
The work done by the electric field in taking unit positive charge from infinity to the point is $\displaystyle \int_\infty ^r \vec E \cdot d\vec r$
The potential at point $r$ is $V_r - V_\infty = V_r = \displaystyle \int_\infty ^r \vec E \cdot d\vec r$
Your uncertainty seems to come from what to do with $\vec E \cdot d\vec r$.
Since the path is radial there will be no angular dependence and so the dot product will be $E\; dr$ where $E$ is positive if the electric field is radially outwards or negative if the electric field is radially inwards.
The $dr$ is just a step length and its direction is taken care of by the limits of integration.
On working out $\displaystyle \int_{\infty}^{r} \dfrac {kq}{r^2}\;dr$ you get $- \dfrac {kq}{r}$ as the work done by the electric field.
If the path had been in the opposite direction ie from $r$ to $\infty$ the work done by the electric field would have been $+\dfrac {kq}{r}$.
This is exactly what you should expect.
With the first integral the force is outwards (positive direction) and the path is inwards (negative direction) and so the dot product will be negative.
With the second integral the force is outwards (positive direction) and the path is outwards (positive direction) and so the dot product will be positive.
To finish off remembering that the potential at a point is minus the work done by the electric field in taking unit positive charge from infinity to the point we get
$V_r – V_\infty = V_r = - \left ( - \dfrac {kq}{r } \right ) = + \dfrac {kq}{r } $
So in your original equation $\displaystyle V(r) - V(\infty) = -\int^r_{\infty} \vec{E}\cdot d\vec{\ell}$ is minus the work done by electric field.
The second definition is that the potential at a point is the work done by an external force in taking unit positive charge from infinity to the point.
For the external force to move the unit positive charge this force must equal $-\vec E$ and so the work done by the external force in taking unit positive charge from infinity to the point is
$\displaystyle \int_\infty ^r \left(- \vec E \right)\cdot d\vec r$
which is the same as
$\displaystyle - \int_\infty ^r \vec E \cdot d\vec r = $ minus the work done by the electric field.
Doing the integration remembering that the external force is $-\vec E$ gives
$\displaystyle \int_\infty ^r \left(- \dfrac {kq}{r^2}\right) dr = + \dfrac {kq}{r} = V_r$ as before.
So rewriting you original equation slightly $\displaystyle V(r) - V(\infty) = \int^r_{\infty} \left(-\vec{E}\right)\cdot d\vec{\ell}$ is the work done by the external force.