Where should an encryption key be stored?
I'm hardly a security expert but if someone can get to your filesystem or your db, you'd be screwed either way—so what you're really doing is technically obfuscation and not really encryption. Ideally you'd do the crypto on a different server or have a hardware module that does the encryption and sends the result back but that solution probably won't work here.

Like you mentioned, if you're storing data in the database, don't keep your key in the db. That would be like taping the combination to the outside of a safe. If someone got a dump of the database, they'd be able to use the key to decrypt the data, obviously. 

Keep it simple. I'd probably opt for somewhere in the filesystem, like in your plugin's config for example. Leave the key blank until you're ready to use the plugin for production and then have the user fill in the value... maybe with something like WordPress's Secret key generator... that way, nobody has the same key even if someone were to get a copy of your plugin's source code.