The article concerns the optimal control of semi-Markov processes with general state and action spaces. The optimal control problem is formulated on finite horizon. We prove that the value function and the optimal control law can be represented by means of the solution of a class of backward stochastic differential equations (BSDEs) driven by semi-Markov process or, equivalently, by the associated random measure. To this end we study this type of BSDEs and under appropriate assumptions we give results on well-posedness and continuous dependence of the solution on the data. Moreover we prove a comparison principle. Finally we show that the BSDEs can be used to solve a nonlinear variant of Kolmogorov equation. As consequence, the un...