mrkgnao: By "first King's Bounty", do you mean the original game from 1990, or King's Bounty: The Legend?
I have never played the former, but have played the latter three times from start to finish (once on Normal difficulty, twice Impossible).
Assuming you mean The Legend, then, while there is some randomisation in what you get as options on level up and a few of the armies you can recruit in some places, its overall effect is quite minimal. AFAIK, no matter what you get, you can complete the game. I wouldn't worry too much about it. I have never had to recreate a character.
This does not mean you don't have to choose wisely your level up bonuses, it just means that what you'll get to choose from will be more than enough. It's a very well balanced game.
Yes it is The Legend. I have this OCD to max min everything, so the randomness is eating at me.