Thank you for the "pip install" advice! That's helpful.

            parts = urlparse(kvstore_endpoint, scheme=self.CONSUL_DEFAULT_SCHEME)
            if parts.hostname:
                args['host'] = parts.hostname
            if parts.port:
                args['port'] = parts.port
            if parts.scheme:
                args['scheme'] = parts.scheme

I feel you're being very forgiving, here. I would prefer to be able to make stronger assertions about what is true at this point. Maybe you're trying to support 'file:///x.txt' URLs? No, I don't really believe that. If we managed to parse a webserver address, I'd expect all three of those to be supplied or defaulted, or we should raise a 'missing part' exception. I think all three are present for all unit tests.

def create_if_not_present(self, full_key: str, value: Union[str, bytes]) -> bool:

Maybe value really does need to be bytes sometimes, but it makes me nervous about callers being sloppy with encoding. Might try sticking with str, see what that impacts, and convince those callers to be more careful.

On the whole your code is easily readable, thank you. You even separated the standard and vendor libraries, kudos. Tiny nit: in get_source(), PEP8 asks for blanks on either side of + operator. I recommend letting flake8 take a pass over *.py.

Things start to get interesting with the (well-named) create_if_not_present(). I wouldn't have minded a comment that mentioned https://python-consul.readthedocs.io/en/latest/#consul.base.Consul.KV.put , but that's just because I'm new to Consul, perhaps it's overkill. The bool type is helpful, but I feel it's still worth adding a brief docstring:

"""Predicate, returns False if the update has not taken place."""

Hmm, return val.decode(), interesting, thank you for teaching me something. I usually specify utf8, but that is default. I wouldn't mind seeing a -> str: return type annotation on _decode_consul_data_value().

In _monitor(), please phrase it this way:

    index_map = {key: index for key, index in results}

(or k, i as you later phrase it).

The idea is that [the KvConfigStore interface] can be swapped for [a non-Consul] implementation if needed

That's an interesting remark. I would believe it more if it mentioned a particular competing implementation, and especially if there was rudimentary code support for it. The most violence happens to the code upon first encounter with 2nd implementation. After that's working, adding support for a 3rd implementation would likely be not such a big deal. If you want to get a feel for amount of risk mitigation you're getting, I'd advise supporting some 2nd implementation now. But I suspect that Consul will be a good match for your needs, and that this "swap out" goal is not an important one to you, that it would be better to revisit the goal after there's a particular bridge you have to cross.

BackgroundTask looks nice enough.

In TestConsulServer, is_open_port() and find_free_port() both call .close(), which suggests that you might insert a with clause.

The dotted quad hardcode is not a big wart, but to eliminate it you might pip install and then consult netifaces.ifaddresses('eth0')[AF_LINK]

You probably want setUpClass to store this often used value: 'localhost:' + str(self.consul_server.api_port)

Test coverage looks very good. I imagine coverage measurements come up mostly green. This is some nice solid library code.