So after some research and fidling around, I did manage to work around this issue. I'm putting this as an answer here, in case other people run into the same problem:
I installed the Plex Media Center on a MacBook running Mavericks as well, and there the installation and first startup ran smooth. I checked the Plugins folder, and it was full of plugins! So I copied over the Plug-ins
and Plugin Support
folder from the MacBook to the iMac and everything is running as expected now.