Should I fix the k-point density and then increase the energy cutoff in steps until convergence, or should I fix the energy cutoff and then increase the k-point density in steps?
What program are you using? You can fix the k-point sampling and increase the energy cut-off and viceversa. At the end, you will use the converged k-point set and energy cut-off.
Both of them, and at the end double-check the convergence. You have to check that the property you're interested on is converged, for example, to obtain converged surface energies, the values used for total energy will not be in general sufficient
Both of them. You can fix the k-point density and find the converged energy cutoff values. Then, with the converged energy cutoff find the converged k-point density.
You can check k-sampling convergency by monitoring the changes in the energy and the density of states. The energy is usually converged first, and the density of states can take a little more. For the planewaves you can probably just check the energy, but people tend to use a hight cutoff directly (just like double-Z or triple-Z basis sets are the minimal standard in quantum chemistry for molecules).