Does constant perpendicular force always cause uniform circular motion?

Let me suggest thinking about it like this: start with Newton's second law, $\vec{F} = m\vec{a}$. As a vector equation, it applies in any direction you care to choose: the component of force in that direction is proportional to the component of acceleration in that direction.

So, think about your moving object at a particular moment in time, and take the "forward" component of the equation - that is, choose the direction that it happens to be moving in at that moment. $$F_{\text{direction of motion}} = ma_{\text{direction of motion}}$$ The component of force in the direction of motion is zero (do you understand why?), so the acceleration in the direction of motion is zero, and therefore the rate of change of speed is zero: the object is not speeding up or slowing down.

Now, consider the perpendicular direction. $$F_{\text{perpendicular direction}} = ma_{\text{perpendicular direction}}$$ Since the object is subject to a certain force, that means it is undergoing a certain acceleration perpendicular to itself. Therefore, its path is curved as if it were part of a circle with some radius. (Does that make sense?) At any later time, the object has moved, and is traveling in a different direction, but it's still feeling the same perpendicular force, and it still has the same mass, so it is still undergoing the same perpendicular acceleration, which means it's still moving along a path curved as if it were a circle of a certain radius - the same radius from before. (Does that make sense?) Since the object path is always curved, and always curved by the same amount, does it make sense that it will move in a circle?

I've deliberately avoided figuring out what the radius of that circle is, because I think it's possible to answer your question without that - in fact, it may even be easier to answer the conceptual question without getting bogged down by having to calculate what the radius is. But as you suspect, when you know how quickly the particle is moving, what its mass is, and what force acts on it, it is possible to calculate the radius of its motion, and that will turn out to be $r = \frac{mv^2}{F}$.