Scheme: FSM substring search
My suggestions are less about your design of the automaton, but rather a few comments on the style and language which I hope you will find useful.

Know your functions
Note that, string-null? is #t if the string has zero length. Thus, if ((string-null? str) "") is the same as if ((string-null? str) str). And that combines well with the else part in max-suffix-that-is-prefix which also returns str.

  (define (max-suffix-that-is-prefix str)
    (if (string-prefix? needle str)
        str
        (max-suffix-that-is-prefix (string-tail str))))


Named let
I noticed that some functions (enumerate and run-automata) define local functions only to then call them with initial values. Scheme provides a syntactic form for that, the named let:

(let proc-id ([id init-expr] ...) body ...+)

More on named let: https://docs.racket-lang.org/reference/let.html

Adhering to the declarative paradigm
The enumerate function could be written in a declarative style. To enumerate from start to end is to cons start to the enumeration from (+ start 1) to end.

(define (enumerate start end)
  (if (= start end)
      `(,end)
      (cons start (enumerate (+ start 1) end))))


Note, however, that this is not an equivalent formulation of the iterative style using an accumulator since the call the enumerate in the call to cons prevents tail-recursion optimisation.

Cleaner syntax using a named let:

(define (enumerate start end)
  (let iter ([start start] 
             [end end] 
             [acc '()])
    (if (&gt; start end)
        acc
        (iter start (- end 1) (cons end acc)))))