Just because mailboxes hosted on your VPS are sending out spam, it does not mean that your server was compromised. A script may have maliciously accessed their email credentials from anywhere and is now subsequently able to access as and when they like to distribute thousands of spam emails to huge email lists (or, most likely to everyone in that mailboxes contacts/address book) Here is a similar scenario of this happening.
The best way to diagnose this would be to change the password to the particular mailbox sending the spam and don't advise the end user of the password straight away. Then see if the sending of spam from that mailbox halts (by analysing the mail logs on the VPS and monitoring the mail queue).
If literally, everyone on your VPS is affected, then I'd analyse your access logs to see exactly where the access is coming from and how they're accessing (you may have to dive into multiple logs to identify this).
If their emails are being spoofed (it doesn't sound like it though if they appear to come from themselves), then this may be useful.
If you did want to create an SPF record though, you have to set this up as a TXT record in the DNS zones. What the TXT record contains is entirely down to your VPS setup though but you can use an online generator such as this one.