Why can't we have "Company" criteria too in leave allocation tool?

You can, but the Leave Control Panel is not available through the “Customize Form” option in Setup, which means the safest way to add a new field there is with a custom app, or coding it and making a pull request on Github.

The Leave Control Panel itself is not a document that gets saved, instead it creates documents in bulk. There would be little point in adding a custom field there without modifying the tool’s server side code to push the new field to the created documents. I think that’s why it’s not made to easily accept a custom field.

So options are custom app, paid develoment job, or feature request on Github. Until the feature is there you CAN easily create a custom “Company” field in the Leave Allocation Form, just not the tool.