A user can start physical replication without needing CONNECT on any database if it has REPLICATION attribute. That means any user that is allowed logical replication on a specific database (or even no databases) can replicate the whole cluster using physical replication. I don't think it is a proper behavior from the security perspective.
Physical replication has a special entry in pg_hba.conf, hence, I don't think you need CONNECT on all databases. However, logical replication uses the same entry from a regular connection and I concur with Michael and Stephen that we should have LOGIN and REPLICATION privileges in those cases. If we drop the LOGIN requirement for logical replication, it means that a simple NOLOGIN won't be sufficient to block a certain role to execute queries because "replication=database" could be used to bypass it. Physical replication can't execute queries but logical replication can. IMO REPLICATION is an additional capability and it is not a superset that contains LOGIN. I prefer a fine-grained control. In sections 26.2.5.1 and 30.7, LOGIN are documented accordingly. I'm +0.5 to the idea of adding a WARNING when you create/alter a role that has REPLICATION but not LOGIN.