While there are good reasons behind the toy safety standards, this comment by pojo-guy is also part of the truth:
I believe the motivation is a simple fear of lawsuits.
I have seen those "not for children under 3 years" warnings on books and other kinds of objects that do not seem to pose any particular choking hazard, and even when very similar toys are sold with a marking of 1+ years.
The reason is probably that the relevant toy standards have a lot more safety tests that have to be done for toys intended for children under 3 years. Quoting from EN71 which is the toy safety standard for EU market area:
Toys intended for children under 36 months shall in addition to relevant requirements of Clause 4 conform to
the following requirements ...
a) Toys and removable components of toys shall not, whatever their position, fit entirely in the cylinder when
tested according to 8.2 (small parts cylinder)
b) When tested according to 8.3 (torque test), 184.108.40.206 (tension test, general), 8.5 (drop test), 8.7 (impact test)
and 8.8 (compression test), ...
The list continues up to g), and that is only the general requirements, with more requirements following for toys with soft filling, for toys with cords etc. The required tests are quite comprehensive and probably quite expensive if you buy it as a service from some certified testing company.
Compared to this, the requirements in "Clause 4" that apply to all toys, are mostly common sense and most of them do not have mandatory testing. So if you just put "over 3 years" label on the product, it is much easier to satisfy the requirements of the standard. Whereas if you want to legally sell a toy for children under 3 years in Europe, you usually need to perform a long series of tests.