Problem solved. These are the complete steps (for reference):
1. stop dcm4chee
2. backup JBM_MSG_REF table:
$ mysqldump -u root -p pacsdb JBM_MSG_REF > JBM_MSG_REF.sql # Username might be different on your system
3. clear existing values in PAGE_ORD column (it will be populated automatically again):
$ mysql -u root -p pacsdb
> update JBM_MSG_REF set PAGE_ORD = NULL;
> quit
4. start dcm4chee
5. check if it works (the MoveScu service should be running again and work on existing messages)
6. optionally: make wild dance moves in the office and feel like a hero :-)
PS: The error happened probably because I tried to clear the message cue.