For me, personally, validation rules are about the messages that end up being presented to your end users. Well, that and making sure that your data quality remains high. The important part for your users, however, are the messages that result from failing validation.
Validation rules can only display a single error message, and either on one field or at the top of the page. Sure, you could mash everything into a single validation rule, but would the resulting error message be clear to your users?
The way you've described your validation rule criteria makes it sound like they should be broken up into 3 validation rules.
- The first one (require lookup populated) should say something about "lookup needs to be populated when changing lead stage to {stage name here}", and the appropriate location here is probably the lookup field (the issue isn't that the lead stage changed, it's that the stage changed and this lookup is empty)
- The second one (executive change to certain stage) should mention the target profile in the error message, and be put on the stage field (the issue is a change being made to stage by the wrong person)
- The third one (sales change to certain change) is similar to the second rule, but the target of your message is different (we need to be in this stage before changing to that stage)
You could cram the second and third validation rules together, but then your message would be something like "Only Execs can change to exec qualified, or needs to be exec qualified before converting", which is (in my opinion) a lot less clear than seeing the individual messages separately.