Shortest-depth routing algorithm
Problem statement

Define the function $f$ by

$$f(a_1,\dots,a_k) = \sum_{i=0}^k \prod_{j=1}^i a_i.$$

In other words,

$$f(a_1,\dots,a_k) = 1 + a_1 + a_1 a_2 + a_1 a_2 a_3 + \dots + a_1 \cdots a_k.$$

Given $n$, you are looking for $a_1,\dots,a_k$ that form a solution to the equation

$$f(a_1,\dots,a_k) = n.$$

A useful lemma

Let me point out a useful property of the function $f$:

$$f(a_1,a_2,\dots,a_k) = 1 + a_1 f(a_2,\dots,a_k).$$

This follows immediately from the identity

$$1 + a_1 + a_1 a_2 + a_1 a_2 a_3 + \dots + a_1 \cdots a_k = 1 + a_1 (1 + a_2 + a_2 a_3 + \dots + a_2 \cdots a_k).$$

An algorithm for your problem

Now we get a reasonable algorithm for your problem, using dynamic programming.

Each subproblem is indexed by $(i,n')$, and records the best sequence $a_i,a_{i+1},\dots,a_k$ such that $f(a_i,a_{i+1},\dots,a_k)=n'$.  Now we can find the best solution to the original problem by enumerating all possible values for $a_1$, then looking for a solution to the $(2,(n-1)/a_1)$-subproblem.  And, we can solve the $(i,n')$-subproblem by enumerating possible values of $a_i$ and looking for a solution to the $(i+1,(n'-1)/a_i)$-subproblem.  Of course, as a straightforward optimization, we can limit our search to only values of $a_i$ that are a divisor of $n'-1$.

How many subproblems are there, in all?  A simple bound is that there are at most $kn$ subproblems, so the running time of this algorithm is at most $O(kn^2)$.  Using the optimization, I expect the running time will be much less in practice, as most values of $n'$ have only a limited number of divisors.  (See also this question for a math question that is related to the efficiency of this dynamic programming algorithm.)

Another optimization

Here is one more optimization you could apply.  You could use modular arithmetic to quickly filter out subproblems that have no solution.

Suppose we have a small prime $p$, and we have fixed values of $k,n$.  Then if there exists a solution to $f(a_1,\dots,a_k) = n$, then there exists a solution $f(a_1,\dots,a_k) \equiv n \pmod p$; conversely, if there is no solution to $f(a_1,\dots,a_k) \equiv n \pmod p$, then there is no solution to $f(a_1,\dots,a_k) = n$.

So, we could pick a small prime $p$, and then tabulate for which values of $(i,n')$ the $(i,n')$-subproblem has a solution.  Note that we only care about the value of $n'$ modulo $p$, so there are only $kp$ such subproblems, and we can enumerate which ones have a solution in $O(kp^2)$ time using dynamic programming.  (We cannot use the divisibility optimization any longer.)

So, we could precompute a table of size $kp$ and use it to filter out subproblems.  Before trying to solve the $(i,n')$-subproblem, we first look up $(i,n' \bmod p)$ in our table to see whether it has a solution modulo $p$.  If it doesn't have a solution modulo $p$, we don't try to explore that subproblem (we don't try to look for a solution in the integers; we know it'll fail).

We can build a table for each of a handful of small primes, say $p=2,3,5,\dots,17$, and check against each of these tables before exploring a subproblem.  This might reduce the number of subproblems that have to be explored, and thus improve efficiency.

Can we use this idea plus the Chinese remainder theorem to solve the original problem?  Unfortunately not: the requirement that $a_i \le m$ does not behave well under modulo arithmetic.  Thus, if all we wanted to know is whether there exists some sequence of positive integers $a_1,\dots,a_k$ satisfying $f(a_1,\dots,a_k)=n$, then we could solve that in $\text{poly} \log (n)$ time by looking for a solution modulo a set of small primes whose product exceeds $n^k$, then applying the Chinese remainder theorem.  However, your question asks whether there exists a sequence $a_1,\dots,a_k$ satisfying $f(a_1,\dots,a_k)=n$ such that $a_i \le m$ for each $i$, and that cannot be solved efficiently in such a way.  If you were willing to drop the requirement that $a_i \le m$, then your problem could be solved a lot more efficiently.