Leadership question: if you empower a Follower (enhance his CR), it leaves you?

[Duke of Urrel]

Your followers are of much lower level than you. They are not able and probably not willing to face the dangers that you are able to face as a high-level character. If you have the Leadership feat, your followers are your admirers, but they don't necessarily want to be your fellow travelers.

This is about all that I can gather from the Rules as Written. The rest is between you and your dungeon master.

Keeping this in mind, I think I'll try to answer your two main questions in reverse order.

What is the difference between a Follower and a Helpful, well paid hireling?

To answer this question, I will refer to my own house rules that I use when I'm the dungeon master.

As a house rule, I require followers by default to be Friendly toward the PC who is their leader, who is always a PC with the Leadership feat. Indeed I require followers usually (that is, two-thirds of the time) to have the same moral and ethical outlook as the PC who is their leader. If you are a PC with the Leadership feat, I require your followers to choose to live near your home, if you have one. Your home is the place where you regularly rest between adventures. If you don’t have a home, your followers choose to live in a place where you are well known but also where they can easily find shelter, work and natural resources to sustain themselves. Whenever you are resting at home – or in the place where your followers live if it is not your home – I allow you to request favors from your followers as if they were all contacts. For details, refer to pages 153 to 154 of the DUNGEON MASTER'S GUIDE II v. 3.5 (2005).

Since followers are low-level NPCs, they are not interested in taking great risks for you. They will fight to defend you only if your resting place, which is also their home, comes under attack. As a house rule, I allow you to use Diplomacy to persuade a follower to leave their home and accompany you on an adventure. When you do, I require your follower’s attitude immediately to drop from Friendly to Indifferent, and the follower agrees to accompany you on an adventure only if you raise its attitude to Helpful. If your follower becomes Helpful, they agree to accompany you on an adventure, but when your adventure begins, their attitude drops back to Friendly again. For as long as your follower accompanies you on your adventure, you must pay your follower the standard daily wage of a hireling, including hazard pay, but your follower is more loyal than a hireling would be.

If you are a PC with the Landlord feat as well as the Leadership feat, you can easily hire some of your followers to guard or to maintain your stronghold. You don’t even have to use Diplomacy skill to persuade them, and they are more loyal to you than ordinary hirelings. However, you must pay a monthly salary to every follower whom you hire to help guard or maintain your stronghold. For details, refer to the STRONGHOLD BUILDER'S GUIDE v. 3.0 (2001).

On to the next question!

If a willing follower becomes more powerful due your actions - for example, if you are a werewolf and he asks to become a packmate, or if you turn him into a Stone Warrior, or any other template that can be added to a living humanoid - what happens?

He stays your follower? He becomes a friendly hireling? He says goodbye and leaves?

This is something to discuss with your dungeon master. Normally, followers don't advance in level at all, and allowing all of your followers to advance would be seriously bending the rules. But allowing only one of your followers to advance? I don't think this is a serious problem. Maybe advancing one follower should be allowed, but maybe the price for this privilege should be that you won't be allowed to attract quite as many higher-level followers later, when you advance and your Leadership score rises. This is what I would decide if I were your dungeon master.