Found out the answer to my question after a lot of reading and some experimentation. Summarising here in case anyone runs into similar problems because it can be hard to find the answer without knowing exactly what to search.
For context, our previous implementation of layer 2 switching and VLAN is identical to Cumulus Linux's Traditional Linux Bridge Mode. A bridge is created for each VLAN. A trunk port is implemented by adding VLAN-tagged subinterfaces and each of those subinterfaces is added to the corresponding VLAN in the trunk access list. See the Cumulus user guide page for some configuration examples.
To answer question 2: no, turning on Linux STP instances for each VLAN does not make this PVST+ or compatible with PVST+. PVST+ involves more than sending out VLAN-tagged BPDU packets: the destination MAC address is different, the SNAP header is present, and a field is added in the payload to carry VLAN information. The Cisco switch on the other side will not accept the VLAN-tagged 802.1d BPDU packets, nor will any VLAN other than the native VLAN of the trunk port (over which PVST+ sends 802.1d BPDUs corresponding to VLAN 1 topology for backwards compatibility) receive any BPDU. It won't work at all.
Our current implementation uses the VLAN-aware bridge, available in mainline Linux since 3.9. A single instance of STP runs for all the VLANs. This is interoperable with MSTP: conceptually, it's as if we were running MSTP with all VLANs mapped to a single MST instance. So, to answer question 1, Linux does not do MSTP, but STP + VLAN-aware bridge is interoperable with MSTP.
EDIT:
You might wonder how Cumulus does PVST+. The answer is that they run a patched kernel with their own implementation of PVST+. Also, a big pitfall to avoid: MSTPD does not do PVST+ despite their claim. We are looking into extending it for PVST+ support.