K (ngn/k), 60 53 52 49 40 bytes

-9 bytes from @doug

#,//(-1+11\'256!0x3e566240af0097281a26)/

Try it online!

Takes input as two separate arguments; hops as the first, keys as the second.

Uses a list to map keys to each other key a "hop" away. When combined with /, this functions as a finite-state machine, seeded with key and run for hops iterations. ,// flattens the result into a one dimensional array and # takes its count.

Note that -1+11\'256!0x3e566240af0097281a26 is a compressed version of (4 6;6 8;7 9;4 8;0 3 9;!0;0 1 7;2 6;1 3;2 4), i.e. a list mapping indices to other digits a knight's move away.

Python 2, 68 bytes

Saved 1 byte thanks to @Sisyphus
Saved 5 more bytes thanks to @xnor

This is based on the logic used in my 62-byte JS version, with a different implementation to make it easier to golf in Python. I've since ported this back to JS, as it turned out to be shorter as well.

f=lambda n,k:n<1or k-5and(2-k%2)*f(n-1,4-k%-9%2)+9%~k%2*f(n-1,k%2*2)

Try it online!

Below is a summary of the results returned by each expression, split by key groups:

 expression | 1 3 7 9 | 2 8 | 4 6 | 0 | description
------------+---------+-----+-----+---+---------------------------------------
 2-k%2      | 1 1 1 1 | 2 2 | 2 2 | 2 | weight for the 1st recursive call
 4-k%-9%2   | 4 4 4 4 | 3 3 | 3 3 | 4 | target key for the 1st recursive call
 9%~k%2     | 1 1 1 1 | 1 1 | 0 0 | 0 | weight for the 2nd recursive call
 k%2*2      | 2 2 2 2 | 0 0 | - - | - | target key for the 2nd recursive call

Java 8, 137 129 91 89 bytes

int f(int n,int k){return--n<0?1:k%2>0?k==5?0:f(n,2)+f(n,4):2*f(n,k>0?1:4)+k/4%2*f(n,0);}

Port of @Arnauld's JavaScript answer, provided by @OlivierGrégoire.
-2 byte thanks to @ceilingcat.

Try it online.

Old 137 129 bytes answer:

(s,h)->{for(;h-->0;){var t="";for(var c:s.getBytes())t+="46,68,79,48,309,,107,26,13,24".split(",")[c-48];s=t;}return s.length();}

Starting digit as a String input, amount of hops as an integer.

Try it online.

Explanation:

(s,h)->{                    // Method with String & integer parameter & integer return
  for(;h-->0;){             //  Loop the integer amount of times:
    var t="";               //   Temp-String, starting empty
    for(var c:s.getBytes()) //   Inner loop over the digit-codepoint of the String:
      t+=                   //    Append to the temp-String:
         "46,68,79,48,309,,107,26,13,24".split(",")[c-48]);
                            //     The keys the current digit can knight-jump to
    s=t;}                   //   After the inner loop, replace `s` with the temp-String
  return s.length();}       //  Return the length of the String as result

JavaScript (ES6),  62 61  60 bytes

My Python port, ported back to JS. :-p

f=(n,k,o=k%2)=>n--?k-5&&(2-o)*f(n,!k*3-~o)+(k&5&&f(n,o*4)):1

Try it online!

Below is my original 62-byte version, which is easier to understand:

f=(n,k)=>n--?k&1?k-5&&f(n,2)+f(n,4):2*f(n,k?1:4)+(k&4&&f(n)):1

Try it online!

How?

There are 4 groups of keys which are really connected together. All keys within a group have the exact same behavior.

• Corners 1, 3, 7, 9 (in green). Characterization: odd keys that are not equal to \$5\$.
• Left/right sides 4, 6 (in blue). Characterization: even keys for which we have \$k \operatorname{and}4 = 4\$.
• Top/bottom sides 2, 8 (in yellow). Characterization: non-zero even keys for which we have \$k \operatorname{and}4 = 0\$.
• The 0 key (in red).

The 5 key is secluded and processed separately.

The figure on the right is a weighted directed graph showing which target groups can be reached from a given source group, and how many distinct keys are valid targets within each target group.

This algorithm does one recursive call per target group from the current group, multiplies each result by the corresponding weight and sums them all.

Only the first iteration is expecting \$k\in[0..9]\$. For the next ones, we just set \$k\$ to the leading key of each group (\$1\$, \$4\$, \$2\$ and \$0\$ respectively).

JavaScript (ES6),  86 74  72 bytes

f=(p,n,k=10)=>n?k--&&(306>>(p*2149^k*2149)%71%35&1&&f(k,n-1))+f(p,n,k):1

Try it online!

71 bytes

Much, much slower.

f=(p,n,k=10)=>n?k--&&(306>>(p*2149^k*2149)%71%35&1)*f(k,n-1)+f(p,n,k):1

Try it online!

Finding a hash function

We are looking for a function \$h(p,k)\$ telling whether \$p\$ and \$k\$ are connected by a knight hop. Because this function is commutative and because the result is always the same when \$p=k\$, a bitwise XOR looks like a good candidate.

We can't directly do \$p \operatorname{XOR} k\$ because, for instance, \$0 \operatorname{XOR} 4\$ and \$3 \operatorname{XOR} 7\$ are both equal to \$4\$ although \$(0,4)\$ are connected and \$(3,7)\$ are not.

We need to get more entropy by applying some multiplier \$M\$ such that \$(M\times p)\operatorname{XOR}\:(M\times k)\$ is collision-free. The first few valid multipliers are \$75\$, \$77\$, \$83\$, ... (We could apply two distinct multipliers to \$p\$ and \$k\$, but we would lose the benefit of the function being commutative. So it's unlikely to lead to a smaller expression.)

For each valid multiplier, we then look for some modulo chain to reduce the size of the lookup table.

By running a brute-force search with \$M<10000\$ and two modulos \$1<m_0<m_1<100\$ followed by a modulo \$32\$, the following expression arises:

$$h(p,k)=((((p\times 2149)\operatorname{XOR}\:(k\times 2149))\bmod 71)\bmod 35)\bmod 32$$

We have a valid hop iff \$h(p,k)\in\{1,4,5,8\}\$, which can be represented as the small bit-mask \$100110010_2=306_{10}\$.

Hence the JS implementation:

306 >> (p * 2149 ^ k * 2149) % 71 % 35 & 1

Note that the final modulo \$32\$ is implicitly provided by the right-shift.

Commented

f = (                       // f is a recursive function taking:
  p,                        //   p = current position
  n,                        //   n = number of remaining hops
  k = 10                    //   k = key counter
) =>                        //
  n ?                       // if n is not equal to 0:
    k-- && (                //   decrement k; if it was not 0:
      306 >>                //     right-shifted lookup bit-mask
      (p * 2149 ^ k * 2149) //     apply the XOR
      % 71 % 35             //     apply the modulo chain
      & 1 &&                //     if the least significant bit is set:
        f(k, n - 1)         //       do a recursive call with p = k and n - 1
    ) +                     //
    f(p, n, k)              //     add the result of a recursive call
                            //     with the updated k
  :                         // else:
    1                       //   stop the recursion
                            //   and increment the final result

T-SQL, 197 bytes

Returns null for no solutions

This can handle 25 hops in 10 seconds

WITH C as(SELECT 0i,1*translate(@n,'37986','11124')x,1q
UNION ALL
SELECT-~i,y,q*(2+1/~(y*~-a))FROM(values(1,4),(1,2),(4,0),(2,1),(4,1),(0,4))x(a,y),c
WHERE a=x AND i<@)
SELECT
sum(q)FROM C
WHERE i=@

Try it online

Wolfram Language, 108 bytes

Tr@MatrixPower[AdjacencyMatrix[4~KnightTourGraph~3~VertexDelete~{10,12}],#2,SparseArray[Mod[#,10,1]->1,10]]&

Try it online!

You know, there's probably a shorter solution for this, but I enjoy the mathematics of this one. This gets the adjacency matrix for the graph, raises it to the power of the number of jumps, and multiplies it by a vector representing which key it starts from. The elements of the resulting vector give the number of paths to each key, so the total gives the total number of paths of a given length.

Python 2, 83 bytes

f=lambda s,n:n<1or sum(f(i,n-1)for i in range(10)if`i`+`s`in`0x20cb0e9fd6fe45133e`)

Try it online!

A recursive solution. Checks for pairs of digits that are a knight's move away by them being consecutive in the hardcoded string 604927618343816729406, written one byte shorter in hex. This string is a palindrome because the adjacency relationship being symmetric, but I didn't see a shorter way to take advantage of that and remove the redundancy.

83 bytes

f=lambda s,n:n<1or sum(f(i,n-1)for i in range(10)if 6030408>>(s*353^i*353)%62%29&1)

Try it online!

85 bytes

def f(s,n):a=b=c=d=1;exec"a,b=b+c,2*a;c,d=b+d,2*c;"*n;print[d,a,b,a,c,n<1,c,a,b,a][s]

Try it online!

A different idea giving a fast, iterative solution. We take advantage of the knight-move adjacency graph of the phone keypad being symmetric:

3--8--1
|     |
4--0--6
|     |
9--2--7 

Note that 0 doesn't break the top-bottom symmetry of the keypad because it connects just to 4 and 6 on the centerline. The number 5 is isn't drawn; it doesn't connect to anything.

We use the symmetry to collapse down to four types of locations:

a--b--a
|     |
c--d--c
|     |
a--b--a 

a: 1379
b: 28
c: 46
d: 5

We now have the transitions (some appearing multiple times):

a -> b, c
b -> a, a
c -> a, a, d
d -> c, c    

This corresponds to the update of counts at each step of a,b,c,d=b+c,2*a,2*a+d,2*c. This can be written shorter as a,b=b+c,2*a;c,d=b+d,2*c, as pointed out by ovs saving 2 bytes.

So, we iterate n steps to produce the correspond values of a,b,c,d, and now we need to select the one corresponding to the start digit s. We need a mapping of each digit 0-9 to the corresponding entry a,b,c,d, with 5 going to n<0. The code just uses a direct array selector: [d,a,b,a,c,n<1,c,a,b,a][s].

There's probably a shorter way using the symmetry that s and 10-s are in the same category, and so we can do something like s*s%10 to collapse these, or even s*s%10%8 to get a distinct fingerprint for each type. With optimizations, this method might take the lead.

Python 3, 88 bytes

f=lambda s,n:n<1or sum(map(f,'46740 021268983 1634    9 7'[int(s)::10].strip(),[n-1]*3))

Try it online!

-15 bytes thanks to ovs

-2 bytes thanks to Jonathan Allan

Jelly,  29  28 bytes

⁵ṗ’;;Ṣe“¡¿Ṅ\ȷḳ€°ị’Ds2¤ʋƝPɗ€S

A dyadic Link accepting the number of hops on the left and the key on the right which yields the number of paths.

Try it online!

How?

Forms all length hops decimal numbers, prepends key to each and counts how many have all valid neighbours by lookup in a compressed list. (Note: when hops is zero the fact that the empty product is one means the Link yields 1, as desired.)

Here is another 28

⁵ṗ’µ;⁴+3!PƝ%⁽W⁶%31fƑ“¤®€×‘)S

This one uses some funky arithmetic to decide whether each move is valid by adding three to each of the two digits, taking their factorials, multiplying these together, getting the remainder after division by \$22885\$, getting the remainder after division by \$31\$, and checking if the result is one of \$\{3,8,12,17\}\$.

Charcoal, 31 bytes

ＦＮ≔⭆η§⪪”)‴↘Ｓ‴Ｐeυ!&q]3⁰4”¶ＩκηＩＬη

Try it online! Link is to verbose version of code. Takes the number of hops as the first input. Too slow for large numbers of hops. Explanation:

ＦＮ

Input the number of hops and repeat that many times.

≔⭆η§⪪”)‴↘Ｓ‴Ｐeυ!&q]3⁰4”¶Ｉκη

Map over every character in the string and list its possible next hops. Example: 6 → 170 → 682646 → 1701379170390170 → ...

ＩＬη

Count the total number of hops found.

Faster 44-byte version:

≔Ｅχ⁼ιＩηηＦＮ≔Ｅ⪪”)∧↑mG@⁰EBü)‽₂≕↖”χΣＥκ×Ｉμ§ηνηΣＩη

Try it online! Link is to verbose version of code. Explanation: Works by repeatedly multiplying a next hop transition matrix.

05AB1E, 24 22 bytes

F•žNjεEÿ¶^²è+%•5¡sèS}g

Amount of hops as first input, and the starting digit as second input.

Try it online or verify all test cases (except for the one with 20 hops, which times out).

Explanation:

F               # Loop the first (implicit) input amount of times:
 •žNjεEÿ¶^²è+%• #  Push compressed integer 46568579548530955107526513524
   5¡           #  Split it on 5: [46,68,79,48,309,"",107,26,13,24]
     s          #  Swap to take the current list of digits,
                #  or the second (implicit) input in the first iteration
      è         #  (0-based) index those into this list
       S        #  Convert it to a flattened list of digits
                #  ("" becomes an empty list [])
}g              # After the loop: pop the list of digits, and take its length
                # (after which the result is output implicitly)

See this 05AB1E tip of mine (sections How to compress large integers?) to understand why •žNjεEÿ¶^²è+%• is 46568579548530955107526513524.

Perl 5, (-p) 63 bytes

eval's/./(46,68,79,48,390,"",170,26,13,24)[$&]/ge;'x<>;$_=y///c

Try it online!