Is there anything else I have to set on the server to get StartTLS working?
Check "man ldapsearch" for -Z[Z] option.
If you want to enforce StartTLS, set appropriate SSF with olcSecurity:
$ ldapsearch -x -H ldap://server ldap_bind: Confidentiality required (13) additional info: TLS confidentiality required
$ ldapsearch -x -ZZ -H ldap://server ... # search result ...