I consider them to be paramilitary, which is basically the same thing.
As a Brit, I see "paramilitary" as something of a negative term, and etymologically such organisations are considered:
Starfleet are described as "not civilian" at least as often and more plausibly given the broader range of definitions as it is "not military", although they are more or less "organised in military fashion".
but which do not represent the formal forces of a sovereign power.
This however is explicitly not the case as Starfleet are consistently depicted as not just a formal uniformed force for the Federartion but either the main or only such force that is permenantly mobilised.
Therefore, I prefer the term "militarised police/naval force" and speculate that Starfleet is something similar to what the US Coast Guard would have become if they had remained the US naval force after the end of the 18th Century.
But YMMV.