4 years later consul is gone in aws for us replaced by this simple dns/alb scheme. We haven't really needed all the features of advanced discovery.
The key in general to "discovery" seems to be load balancers and dns in our approach (service protect thyself vs well behaved clients). Easy to use LBs on aws is very powerful feature. We don't have that on our on prem and it changes how we approach things. There discovery is harder.
But if that's a feature that you want, you can even use Docker Swarm which I mentioned in another comment here, which basically gives you the same thing, so that you can reference other containers by their names.
Of course, it's a bit simpler than Nomad, so if you're already using Nomad then there's no point in moving away from it, though this still illustrates that there are plenty of simpler options than K8s!