In my case it was a configuration problem:

I misunderstood the k3s --cluster-domain option (which feeds into kubelet's --cluster-domain option) to mean the public domain of the cluster. All the k3s documentation offers is "Cluster Domain".

But --cluster-domain must be a private, cluster-internal domain like the default "cluster.local".

By assigning the public domain, I basically removed it from external DNS lookup, i.e. coredns refused to DNS-recurse. Hence the HTTP challenge self check did not work.

Removing the --cluster-domain option (i.e. letting it default to "cluster.local"), and rebooting the cluster solved the issue.