I would go for CoreService for all actions, apart from parts where you have GUI extensions. It's quite quick to write and easy to check. Running these tests will quickly show you the problem. Make sure your tests are able to run multiple times without too many preconditions (for example it generates unique names, independent on each other, few dependencies on environment state)

Next to it you might want to write some GUI automation tests. For this you may indeed use Selenium, only not Selenium IDE, but Selenium WebDriver. You will not be able to click and do other stuff with the default set, but there's very useful feature - ability to run JavaScript code. So instead of command to click on something, you just have a scriplet which says where to click and what to do. You will have to do quite some coding, but it will work. You should be able to catch the script bits with FireBug, or Chrome developer dashboard when doing the same actions in CME. So your test set will have urls and scriplets as input. You may then verify the actions made with CoreService, or Selenium. But also, keep in mind that this internal Tridion stuff and the JavaScript will most probably change from version to version.

The other approach to GUI automation is Visual Studio Coded UI, but it's quite expensive and will also require you to do a lot of coding (although you still might record some bits).