Besides just waiting, there are only two ways to increase the company rating:

1. plant trees around the city (more than one tree per tile has no effect)
2. bribe the local authority (only with TTDPatch)

In case you understand German well enough, read this:
http://www.tt-ms.de/tipps/#vdob