This is allowed by REST as long as your {key} URLs are discoverable; for example if doing

GET /base-url/

returned a list of links to other valid REST resources, and among those were /base-url/{key}

The main point is that out-of-band knowledge can’t be required by a REST-conforming API; but if a provider publishes a specification the client is certainly free to go directly to a URL it already knows about.

I found this article by Roy Fielding useful to clarify these points, in particular

A REST API must not define fixed resource names or hierarchies (an obvious coupling
of client and server). Servers must have the freedom to control their own namespace.
Instead, allow servers to instruct clients on how to construct appropriate URIs, such
as is done in HTML forms and URI templates, by defining those instructions within
media types and link relations. [Failure here implies that clients are assuming a
resource structure due to out-of band information, such as a domain-specific standard,
which is the data-oriented equivalent to RPC's functional coupling].

This essentially means that if you publish a spec and the client/programmer needs that in order to determine the valid URLs, then you’ve created an API but it’s not a REST API. To conform with Roy Fielding’s thesis defining REST, you must make those same URLs discoverable by starting at the root.

Independent from implementing a key-value-store or whatever: you could use HATEOAS to describe your api. This enrichens the plain ressource information with meta-information what to do with your API. So in your example a call to base gives a collection of keys and their values:

GET /baseurl/

gives you a resultset:

    [
    {
        "links": {
            "self": {
                "href": "http://www.yoursite/base"
            },
            "item": [
                {
                    "href": "http://www.yoursite/base/key1"
                },
                {
                    "href": "http://www.yoursite/base/key2"
                },
                {
                    "href": "http://www.yoursite/base/key3"
                }
            ]
        },
        "content": [
            {
                "key": "key1",
                "value": "value1",
                "links": [
                    {
                        "self": {
                            "href": "http://www.yoursite/base/key1"
                        }
                    }
                ]
            },
            {
                "key": "key2",
                "value": "value2",
                "links": [
                    {
                        "self": {
                            "href": "http://www.yoursite/base/key2"
                        }
                    }
                ]
            },
            {
                "key": "key3",
                "value": "value3",
                "links": [
                    {
                        "self": {
                            "href": "http://www.yoursite/base/key3"
                        }
                    }
                ]
            }
        ]
    }
]

A simple GET against your baseurl shows a list of items returned. Each with a link (at least) to the single item (or more if you want to relate several keys to other ressources). From that I – as a consumer – know, that there is a ressource key3 behind the URL http://www.yoursite/base/key3. Analogous I know, that I (eventually) could use the typical HTTP-verbs (HEAD, GET,PUT,POST,DELETE, PATCH). But I can query that ressurce for its capabilities via an OPTIONS-Request. Its answer would contain an Allow-Section, which shows allowed verbs:

Allow: OPTIONS, GET, HEAD, POST, PUT, DELETE

When implemented in this way, your API becomes very intuitive and selfexplaining (independend from the ressources you offer).