Vendor Bill approval workflow by department with multiple approvers. I am planning to create a custyom records to define the approvers by department. Any other best approach?

In our company, we store the department approvers in the Department record itself. Not sure if that's better than storing them in custom records instead. I think each has its own sets of pros and cons

Setting them up at Department level should be fine.

There is a suiteapp by NS for suietapprovals where they enable the department wise approval based on the setup