This particular pair of words isn't at all common (this is one of very few relevant references to "a terrace park" I could find in Google Books). From OED:
terrace 5: A row of houses on a level above the general surface, or on the face of a rising ground; loosely, a row of houses of uniform style, on a site slightly, if at all, raised above the level of the roadway.
So in OP's context, it could be a small urban park/garden area, associated with one or more terraces around it, possibly for the exclusive use of the people who live in those terraces. I believe that in London, for example, some such areas have locking gates, to which only the residents have keys. Note that originally, such terraces were quite grand structures housing the well-to-do, but latterly the term has come to be applied to small cramped houses built together for economy (when UK estate agents advertise a mid terrace house it's usually a rather humble dwelling).
Alternatively, noting OP edit that the author is American, it could be that he's simply using the adjective terrace to indicate that the park is on a slope, with one or more flat "platform" sections naturally occurring or cut into the landscape (OED sense 2: Geol., a horizontal shelf or bench on the side of a hill, or sloping ground.)
This is Stern's guide to the greatest resorts of the world describing the Beau-Rivage Palace hotel:
This elegant, traditional European grand hotel, which originally opened its doors in 1861, sits in a terrace park overlooking Lake Geneva in the heart of the Swiss resort area of Lausanne-Ouchy.
...where as the picture suggests, the area around the hotel probably is landscaped into flat terraces.
EDIT: Okay, curiosity piqued, I couldn't resist chasing this one down. I Googled relief map kiev Zhitomirskaya, and from that map discovered there's a park near that street called solom'yans'kyi lisoparc. Googling that soon found me this picture...
...so clearly it's the second meaning here. Quite a large park in a hilly area with various terraced sections, not a small "residents only" garden/park such as you might find in central London.