You should have a look at the thread pool pattern in Wikipedia, I think this is what you are looking for. The trick is to create n threads once when your service starts, avoiding the overhead of thread creation (see this question on SOthis question on SO) during runtime.
As for your workflow, you may want to consider switching the first two steps:
First check if there are records to process, and if there are, see if your thread pool has a free thread. This is an optimisation problem, you want to reach the decision no processing (because there is no data, or no resources for it) with as little effort as possible. If you reach this decision more often because there is no data to process, check for this first.
Some will argue that this is premature optimisation, but I personally prefer to err a little more on the premature side.
