> Question: are there any opportunities to rewrite this logic in a more "structured" style, or to make any other optimizations?

Because A and C only jump to B it is possible to structure this using only loops and one boolean. Let us use Rust to demonstrate as it lacks GOTO:

    let mut a = true;
    loop {
        loop {
            if a { // state A
                match scan() {
                    0 => { write(1); right(); break }
                    1 => { write(3); left(); break }
                    2 => { write(1); right(); return }
                    3 => { write(2); right() }
                }
            } else { // state C
                match scan() {
                    0 => { write(3); right(); break }
                    1 => { write(1); left(); break }
                    2 => { write(3); left() }
                    3 => { write(2); right() }
                }
            }
        }

        a = loop { // state B
            match scan() {
                0 => { write(2); left(); break false }
                1 => { write(3); right() }
                2 => { write(1); left(); break false }
                3 => { write(2); right(); break true }
            }
        }
    }

Of course it is possible to rewrite this as a single loop if you are willing to accept two bits of extra state rather than one.