The paper you cite, "On the multivariate Horner scheme" (Pena, Sauer) has an explicit algorithm specified on p.3.  The remaining challenge is to penetrate the notation and conventions in the paper
laid out in the first three pages far enough to turn their algorithm presentation into code.

It also seems that this paper (just reading the abstract) specifies an explicit algorithm:
"Evaluation of Multivariate Polynomials and Their Derivatives,"
J. Carnicer and M. Gasca,
*Mathematics of Computation*, Vol. 54, No. 189 (Jan., 1990), pp. 231-243.