Seconding checking out FIRST - their youngest program, Lego League Jr., starts at age 6. FIRST has excellent robotics programs, especially at the middle and high school level.

If you're in the US there's a pretty good chance of finding a team local to you [1]. Even if there isn't, creating one is straightforward, although a little pricey [2].

It looks like the FLL Jr. program uses the WeDo 2.0 kits, which look pretty similar to Mindstorms but at a lower cost.

[1] https://www.firstinspires.org/team-event-search

[2] https://www.firstinspires.org/robotics/flljr/start-a-team

I'd go against mindstorms, that is way to advanced for a 4yo. If you want to go lego, Boost or WeDo is better :-)

I especially went with Boost because I remember debugging minstorms at school and I really didn't want to interupt our play-time with a debugging session :D

Lego have just launched Lego Spike - supposed to be a bit more plug'n'play than Mindstorms so maybe better for younger kids. Haven't looked at it in detail