Amoeboid cell migration is characterized by frequent changes of the direction of motion and resembles a persistent random walk on long time scales. Although it is well known that cell migration is typically driven by the actin cytoskeleton, the cause of this migratory behavior remains poorly understood. We analyze the spontaneous dynamics of actin assembly due to nucleation promoting factors, where actin filaments lead to an inactivation of these factors. We show that this system exhibits excitable dynamics and can spontaneously generate waves, which we analyze in detail. By using a phase-field approach, we show that these waves can generate cellular random walks. We explore how the characteristics of these persistent random walks depend on the parameters governing the actin-nucleator dynamics. In particular, we find that the effective diffusion constant and the persistence time depend strongly on the speed of filament assembly and the rate of nucleator inactivation. Our findings point to a deterministic origin of the random walk behavior and suggest that cells could adapt their migration pattern by modifying the pool of available actin.