Hi I sounds like it's something to do with your K2 Parameters settings, Is the allow front end editing set to yes. I would also check the User Groups did you create a User Group ?.
Also in regards to your original question of not having a Add new item link, I just had a interesting thing happen, I have my site configured a little differently in that I use Community Builder to Handle Login / Registrations / Profiles (looks a bit nicer). Anyway I set the My Page Link to go to the CB Profile/Page but the My Account link took me to the Joomla Profile Page and to get rid of that link William suggested to make a template overide of mod_k2user, which I did & worked perfectly, the interesting thing was that once I did the overide I had 2 (Add new Item) links which made me think of your post. I don't think that's why you still can't add new item, but If you want the Add new item link on top you could do the overide then unpublish / delete the menu item you created.
