If your looking for a project that templates a REST service, you're correct in saying there is no out of the box solution. However, RESTful web services are possible using WCF. The key part is to use several attributes when defining your service functions that let the .NET framework know that the function is not expecting SOAP. The main attribute to use is the WebInvoke attribute.
Here is an example from developer.com:
[OperationContract]
[WebInvoke(Method = "PUT", UriTemplate = "/admin/post/{id}")]
void UpdatePost(string id, Post post);
The above code will actually be defined in an interface for your web service. The interface is created automatically when you create your WCF web service project. The actual code for the function will be placed in the class used to implement the web service.
Check out the article on developer.com for a full tutorial. It might seem overwhelming at first if your new to WCF, but after you dive into it, I'm sure you'll start to pick things up quickly. Here is the link for the artile: http://www.developer.com/net/article.php/10916_3695436_1
To answer all of your questions,
a) In .NET 2.0 you should be able to build RESTful services using WSE2.0, but if you have the option to use .NET 3.5, I would strongly recommend going the route of WCF since it is much easier and is designed with REST in mind.
b) Converting your project won't be hard at all. It's just a matter of targetting the new version of the framework in your project settings. Converting a web service from a WSE2.0 service to a WCF service will be a bit trickier though. The easiest way to do so would be to copy the code from each of the different web service functions into the class where you implement the new version of the function. Copy-Paste shinanigans :)
c) I'm not sure what this starter kit is that you're referring to. RESTful web services should be fully supported in WCF which was fully released as of 3.5
d) It would be helpful to understand WCF at least a little before beginning, but it's not crutial to understand it completely in order to get started. I would recommend just reading through the MSDN article on WCF at least once, and then begin working. I'm sure you will come across other questions as you begin, but you can look up those parts as you come across them.
Anyway, I hope this information helps. Good luck to you.