When I open K3b a System Configuration Problems dialog opens with following 4 problems:

Unable to find cdrdao executable
K3b uses cdrdao to actually write CDs.
Solution: Install the cdrdao package.

Unable to find cdrskin executable
K3b uses cdrskin in place of cdrecord.
Solution: Install the libburn package which contains cdrskin

Unable to find growisofs executable
K3b uses growisofs to actually write DVDs. Without growisofs you will not be able to write DVDs. Make sure to install at least version 5.10.
Solution: Install the dvd+rw-tools package.

Unable to find dvd+rw-format executable
K3b uses dvd+rw-format to format DVD-RWs and DVD+RWs.
Solution: Install the dvd+rw-tools package.

I found libburn and dvd_rw-tools in Software Center and installed them but 2 problems still remain

Unable to find cdrdao executable
Unable to find dvd+rw-format executable