Consul Gateway API & Cert-Manager (LetsEncrypt) with HTTP01-challenge

So I was able to repeat the steps above, and saw the same error.
This error is caused because the annotation consul.hashicorp.com/connect-inject: "true" is missing in the service that is created (as you mentioned in a comment).

There are two possible solutions:

Cert-manager needs to enable pass-through of annotations for gatewayHTTPRoute

It seems that cert-manager allows the pass-through of annotations for their HTTP-01 Ingress Solver (HTTP01 - cert-manager Documentation)
It might be worth your time to put in a feature request to allow this on their gateways too.
We did try to see if we could hack it, we realized that the object used for this internally gets merged into the pod, as shown here. However they do not allow both an ingress and gatewayHTTPRoute solver on an issuer, so that didn’t work.

### This Issuer won't work because it contains both `ingress` and `gatewayHTTPRoute` types
apiVersion: cert-manager.io/v1
kind: Issuer
metadata:
  name: example-issuer
spec:
  acme:
    server: https://acme-staging-v02.api.letsencrypt.org/directory
    privateKeySecretRef:
      name: acme-issuer-key
    email: test@yahoo.com
    solvers:
      - http01:
      # not valid to have both ingress and gatewayHTTPRoute
#          ingress:
#            ingressTemplate:
#              metadata:
#                annotations:
#                  "consul.hashicorp.com/connect-inject": "true"
          gatewayHTTPRoute:
            labels:
              name: example-gateway2
            parentRefs:
              - name: example-gateway # Gateway used for HTTP01 requests
                kind: Gateway

Enable connect-inject by default in Consul (not recommend)

You can use this option to enable connect-inject by default.

This will make sure that every service in the cluster has a connect-inject container created as a sidecar. This is not ideal, however, as you may not want every service registered with Consul. You can specifically turn this feature off per deployment, but this will not work out of the box with cert-manager. They would need to add a way for the user to add annotations to
their main deployments:

➜  ~ kubectl get pods -n cert-manager
NAME                                       READY   STATUS            RESTARTS   AGE
cert-manager-7bd65658bc-47hrf              0/2     PodInitializing   0          44s
cert-manager-cainjector-867cf7f7cc-khbdh   0/2     Init:0/1          0          44s
cert-manager-startupapicheck-vgrd6         0/2     Init:0/1          0          44s
cert-manager-webhook-55cf6bbd97-rfsd6      0/2     PodInitializing   0          44s

The annotation would be:
consul.hashicorp.com/connect-inject: "false"

Also the above annotation would need to be manually added to any deployment in the cluster that you did not want registered with Consul.