For the purposes of certificate validation, the record changes don't need to propagate across the entire Internet (accounting for TTL and cache expirations). The validation servers directly query the authoritative nameservers for the domain as @pjones correctly mentioned (the servers pointed to by the NS records). So those authoritative nameservers are the only thing the changes need to propagate to which is usually on the order of seconds or minutes depending on the underlying DNS software/architecture. Though there are some providers that take much longer.
This gets additionally complex for large providers who may be using anycast where a single nameserver IP address might be served by multiple machines across the globe. So the answer you get may depend on where you are querying the name from. Though for a provider like Cloudflare, that global anycast propagation still seems to happen in roughly 15 seconds after a record change in my experience.