Just my personal opinion, but:
I think this is a choice you should leave up to your children. Whether or not a vegetarian or vegan diet is good, advisable or even ethically required is very much in debate, with good arguments for both sides.
From a medical point of view, I think the general consensus is that vegetarian is ok for children, if it is carefully balanced, while vegan is (at least) discouraged because it is close to impossible ot meet a child's nutritional needs without supplements. So an important point against a vegan diet is that you may harm your child.
For such ambiguous cases, I think the children's wishes should take precedence. You can explain your choice to them in terms they can understand (even a 4-yo should be able to grasp the basic issue), then let them decide. And I would be very wary about a vegan diet (even if they should choose it), because of the concerns noted above.
At any rate, a decision like whether they prefer vegetarianism over eating the birthday cake should be left up to them, as it's really a very personal decision, and one they should be able to make.
Note: My wife is vegetarian (though not vegan), while I am not, and we let our daughter decide for herself - the result is she ocasionally eats meat, but rarely.