Do this:

cdrecord -version

If cdrecord does show up as installed then you likely need to point k3b to it.