Use K8s Deployment Hostname In YAML Config
My idea of where the hostname was coming from was wrong. According to the docs:


  Every Service defined in the cluster (including the DNS server itself) is assigned a DNS name.


and


  Currently when a pod is created, its hostname is the Pod’s metadata.name value.


So the hostname is actually the name of the service. The last sentence in my question says I did not change the service in anyway. That was an unintentional lie. I did change the service name, or else selenium-hub as the hostname would have worked.

Changing HUB_PORT_4444_TCP_ADDR to the .metadata.name of the service got me closer. The connection was timing out, though.

I believed some of the configuration was wrong in my service yaml. So instead of using my yaml file, I created the service via:
kubectl expose deployment &lt;deployment name here&gt;

This created a service and I checked the selenium-hub and the node was finally connected. So there was an issue in my service yaml. To get the correct configuration I exported the currently working service:
kubectl get svc &lt;service name here&gt; -o yaml --export

I copied the exported configuration to my service yaml file and it also worked. Here was the difference between the service yamls

old yaml (copied from GitHub example above)
---
apiVersion: v1
kind: Service
metadata:
  name: selenium-hub-service
  labels:
    app: selenium-grid
spec:
  ports:
  - port: 4444
    targetPort: 4444
    protocol: TCP ------------- [added in new config]
    name: port0 ------------- [deleted in new config]
  selector:
    app: selenium-hub
  type: NodePort ------------- [deleted in new config]
  sessionAffinity: None


I am not sure why adding .spec.ports[0].protocol and deleting .spec.type and .spec.ports[0].name fixed the issue. If anyone could clarify in the comments I would appreciate it.