I hardly ever use stem() myself, so I can't claim to have much experience, but my guess is that stem(x, y, "<fmt>") is likely considered quite practical by whoever uses it. Perhaps the further fmts can be made kwonly, but making linefmt kwonly seems(??) bad for usability.
Moreover, the args parsing code can be much simplified; see #21127.

Will come back after #21127 and decide if we should deprecate nevertheless.

but my guess is that stem(x, y, "<fmt>") is likely considered quite practical by whoever uses it.

It's rather a foot cannon. One can be tempted to define the marker here (which I would consider a more common change than the line). But that does not work. This format string only applies to the stem lines and marker information is silently ignored.

Actually even one of our tests is trying to do that:

Also, the stem3d signature already has linefmt as kw-only.

On a side note, the make_keyword_only decorator cannot be used with the *args case.

@_api.make_keyword_only("3.5", 'linefmt')
def stem(self, *args, linefmt=None, ...)

raises

~/dev/matplotlib/lib/matplotlib/_api/deprecation.py in make_keyword_only(since, name, func)
    436     assert (name in signature.parameters
    437             and signature.parameters[name].kind == POK), (
--> 438         f"Matplotlib internal error: {name!r} must be a positional-or-keyword "
    439         f"parameter for {func.__name__}()")
    440     names = [*signature.parameters]

AssertionError: Matplotlib internal error: 'linefmt' must be a positional-or-keyword parameter for stem()

Regarding your side point, that's because linefmt is already kwonly in the example you give.

@timhoffm do you still want this to be merged for 3.5?

The deprecation reduces the risk of unnoticed misuse, so the sooner this gets in the better. OTOH it's not very important. It should not hold up a release or put somebody under pressure to react to it for 3.5.