Your question includes the key equation, $P=Fv$. Power is the force times the current velocity. Now in a real world setting, the power of an engine varies with speed (as many other answers have shown), but we'll use your idealized setting with an engine that outputs constant power at all speeds up to some maximum power limit, $P_{max}$. You've done the calculations for what happens up to that limit. Your question is what happens after that limit is achieved.
In this regime, we have a constant power, and an obviously increasing velocity. This implies the force must be decreasing. Indeed, the force applied by this idealized car on the road must be $F=\frac{P}{v}$ or else the engine is not achieving these ideals.
Your concern was that the car must either be spinning its tires, such that we use the dynamic friction equation $F=\mu_d mg$ (assuming a normal force of $mg$, as you did), or the car must have tires that are now sticking, such that static friction applies. In your question, you indicate that this means $F=0$, but this is not the case. Were that to be the case, static friction could never apply a force and nothing could be held in place by friction. In reality, the equation for static friction is $F\le \mu_s mg$. The force is whatever force is required to keep the objects stationary with respect to eachother, up to a max limit of $\mu_s mg$, at which point they start slipping. But any amount of force up to that point is valid.
So what will happen is that your car will accelerate off the line. At the start, velocity is zero, so force is infinite... that can't be right! Your idealized car is too idealized! So let's recognize that the spinning of tires at the start permits some "bleeding" of power into heat. So the car accelerates along some velocity curve. That curve will be based on the $f_k$ equations you did. What matters is that the velocity grows, and thus the corresponding force decreases.
At some velocity, the force is so low that the tires succeed in "sticking." At what force this occurs is a very complicated topic, especially with rubber tires when bend and flex and stick and do all sorts of complex physicsy things. But at some point this will occur, because your constant power engine will continue to apply less and less force, thus less and less acceleration.
Once the tires stick, we need to switch over to the static friction regime. In this regime, the force of friction is whatever is needed to satisfy the $F=ma$ equation for the car, so long as it doesn't exceed the maximum (which we've already seen because force only goes down in your scenario, never up). The fact that this force does not need to be 0 (as initially stated in the question) is how our car can keep going fast and faster with no limit (although its acceleration gets smaller and smaller)