Initial thoughts
My idea is to get to a target position like this, with Black to move:
Wherein we've just moved Nd6-c8+ or Ne7-c8+ (doesn't matter which). Thereafter, ...Ka8 Nxb6+ Ka7 Kc8 forces ...Kxb6, yielding Kxb8 and the following position:
In which Black cannot prevent us from playing Ka8 next move and achieving our win condition. It seems to me that getting to the first position is entirely doable given that 1) White's king can catch the Black h-pawn, then take all of the f-pawns via g8, and promote the f-pawn to a knight, and 2) Black's king can do nothing but shuffle a7-a8.
Update 1
So it will take 31 moves to get to the first target position above (White Kd7, White knight c8), counting up the moves as follows (king moves in green, f-pawn/knight moves in orange):
However, I realized there exists an alternate positioning of the king and knight that still allows us to execute our Nxb6+ etc maneuver in an even more efficient manner. See below, also with Black to move:
(Wherein ...Ka8 Nxb6+ Ka7 Kc8 clearly bears out an identical Kxb8-a8 solution.) This configuration takes only 30 moves to get to, mainly because it shaves off two knight moves whilst only adding one king move, as follows:
Therefore the second configuration is the one we aim for.
Now the last critical piece of the puzzle is exacting the placement of the Black king at the moment we reach our target position. Clearly, we assumed that Black's king would be on a7, but is that so after White's 30th move?
This seems answerable by first assuming that Black will not touch his h-pawn. Then, we note that on odd move numbers (1..., 3..., etc), Black's king will be on a7, and on even move numbers (2..., 4..., etc), it will be on a8. Therefore, reaching our target position after White's 30th move will witness the Black king on a7 after Black's 29th move - exactly what we wanted.
However, I don't believe all is well and dandy yet! Given that Black will likely want to draw this out as long as possible, Black can himself lose at maximum one king-tempo by playing his h-pawn an odd-number of moves - for example, 1...h6. Then all the rules of the above are switched - Black's king will be on a7 after even-moves and a8 after odd-moves. To account for this, we insert a White king triangulation at any point, and we revise the number of moves required to reach our target position to 30+1=31. All of this is to ensure that Black's king is on a7 as we play Nd7.
So to conclude, reaching the optimal target position takes, at minimum, 31 moves, after which an additional four moves (31...Ka8 32. Nxb6+ Ka7 33. Kc8 Kxb6 34. Kxb8 any 35. Ka8) are required to reach our win condition. So my guess is 35 moves.
