Solution 1:

This is a wildcard certificate and is valid only for third levels such as name.company.com and not fourth levels as the desired bitbucket.kl.company.com

You need to use another certificate for either the specific domain name or get a wildcard one for *.kl.company.com

Solution 2:

The certificate is for *.company.com. So I get an error:

This is expected behaviour, as @whites11 already pointed out in his answer

The puzzling thing is that some browsers don't complain, and load the page as expected.

The problem here is: The implementation of wildcard certificate handling is pretty bad and especially quite inconsistent across browser vendors and versions. Don't expect them to work consistently on all platforms.

Can I order a certificate specifically for bitbucket.kl.company.com, and not use *.company.com?

Yes you can. You just have to proof the ownership/control of bitbucket.kl.company.com to your favorite CA (e.g. Lets Encrypt) and they will issue said TLS certificate to you.