I am ivestigating queues right now.

I have a subnet I want to lower the internet-access priorities of. So I set up a connection mark ('Learn ROuterOS' Dennis Burgess writes that this less CPU intensive as the mangle has to only match the new connection state and then all following packets belonging to that connection will inherit the mark, saving CPU time).

However, in the Queue Tree, I see only a 'packet mark' option, not a 'connection-mark'.

Does that mean that if I want to use the queues i have to change my mangle rules to match every packet and set a packet-mark?

Yes you have to do some changes, but something of that you already have could be useful. Queues applies to packets marks not to connection marks, but you can use your connection marks to use less cpu. Now you have to create packets mark using old connection marks to have a better performance.