Given a movable object with two wheels (connected through an axis) of which each wheel has a velocity pointing always in the direction the wheel rolls (so we assume perfect friction, no drifting is possible).
An top-down illustration is given below
The black object is the object in question in State $S_1$ at time point $t_1$ while the gray object is the object in question in State $S_2$ at time point $t_2=t_1 + \Delta t$.
How can I calculate $p_{1t2}$ and $p_{2t2}$, given $p_{1t1}$, $p_{2t1}$, $v_{1t1}$, $v_{2t1}$ and $\Delta t$ (where $p$ denotes an absolute position in space)?
Note that all calculations are done in 2D space.
To clarify things, I'm talking about this kind of movement

I finally figured it out myself. I'm giving a detailed solution in case someone else needs this.
Solution
First, we calculate the theoretical position $\vec q_1$ and $\vec q_2$ of each wheel by adding the theoretically traveled distance $$\vec q_1=\vec p_{1t1}+\vec v_{1t1}*\Delta t$$ $$\vec q_2=\vec p_{2t1}+\vec v_{2t1}*\Delta t$$
Second, we construct the two direction vectors of both states $$\vec v_1=\vec p_{2t1}-\vec p_{1t1}$$ $$\vec v_2=\vec q_2-\vec q_1$$
Next, find the intersection of the two lines $$ l_1 = \vec p_{1t1} +a*\vec v_1$$ $$ l_2 = \vec q_1 +b*\vec v_2$$ using Cramer's Rule (like here) which gives us the center $\vec c$ of the arc we want to move along (the turning point).
After that, we get the radius $r$ and arc length $s$ of the arc $$r=||\vec c - \vec p_{1t1}||$$ $$s=||\vec q_1 - \vec p_{1t1}||$$
from which we can calculate the angle $\theta$ we have to rotate around the center $\vec c$ in order to travel the full distance $$\theta = \frac{s}{r} \mbox{sign}( \mbox{atan2}(y_{\vec v2}, x_{\vec v2})-\mbox{atan2}(y_{\vec v1}, x_{\vec v1})) $$
the sign function is needed in order to determine the correct sign for $\theta$ (as it would always be positive otherwise).
Finally, we rotate our original points $\vec p_{1t1}$ and $\vec p_{2t1}$ by $\theta$ radians around our arc center $\vec c$ which gives us the actual destination points $\vec p_{1t2}$ and $\vec p_{2t2}$ that we tried to find.
Examples
Here are some examples.