How massive does a planet need to be to create gravitational lensing? Is it ever possible for starlight to be distorted in a noticeable way from something as small as a planet? 

I'm guessing that the chances of this working are better on a dense terrestrial planet than a gas giant.

How do you calculate this?

Edit: I was unclear, sorry. I'm specifically thinking about lensing that would distort the shape of a star, not just move its position.
You could google "Maccone focal" for the most ardent proponent of this project (and I love it too, the most furthest meaningful mission possible within a life time, and what a view!) But others may have variations of his idea. One should be a bit wary about enthusiasts.

Here's a link to some article where Maccone is cited to explain that planets need 6-17 greater distance to become gravitaional lenses than the Sun needs. Neptune surprisingly happens to be next best after Jupiter: http://www.centauri-dreams.org/?p=15290

Paper (might not be available for free):
Maccone, “A New Belt Beyond Kuiper’s: A Belt of Focal Spheres Between 550 and 17,000 AU for SETI and Science.”

Here are slides from one of his presentations where he explains his calculations more generally, but I think only for the Sun:
http://www.spaceroutes.com/astrocon/AstroconVTalks/Maccone-AstroconV.pdf

And then there's micro gravity lenses! A very different thing in terms of our observation. I now think my answer above misunderstood what you were looking for.