Ah, that was it. Thank you very much. I didn't realize it had to be disabled.

Edit: So for future reference, here's what I did:
in /etc/bluetoot/master.conf add line
DisablePlugins = network

After rebooting I ran these commands (as root)
echo 1 > /proc/sys/net/ipv4/ip_forward
pand --listen --role NAP --master
/sbin/iptables -t nat -A POSTROUTING -o rmnet0 -j MASQUERADE
/sbin/iptables -A FORWARD -i bnep0 -o rmnet0 -j ACCEPT
/sbin/iptables -A FORWARD -i rmnet0 -o bnep0 -m state --state RELATED,ESTABLISHED -j ACCEPT
(add iptables rules as you see fit, these are the bare minimum to communicate from BtPAN to mobile data)

Once the connection was successful, since there was no DHCP server that I knew of, I just configured the interface manually:
ifconfig bnep0 address broadcast broadcast netmask netmask
ifconfig bnep0 up

At the Mac end I gave a static address, and voilà - I was tethered.

Of course these commands should be scripted and wrapped into a nice UI, and DHCP might be nice to reduce the need of configuration at the other end, but there's no technical obstacle to any of this.