The best way I know of to add protein with minimal calories is to substitute all or part of a meal with a low-calorie protein shake mix. I use Whey Gourmet, which gets you 20 grams of protein for 120 calories. There are other mixes like this as well.

Shane would be the best guy to consult regarding the “ideal” balance for someone exercising heavily and trying to build muscle mass. Both Chris and I are low-motivation/low activity folks, whereas Shane has at various times been fairly serious body builder. For myself, I’m happy to get my protein calories up to about 25%, with most of the balance carbs. But I am not aiming for anything approaching ideal- I just want to understand what I’m ingesting so I make better choices at least some of the time.

The one thing I can say is that your measured heart rate sounds too high: if it is correct, that is. For weight loss, you want to be around 60-70% if I recall correctly, and for pure cardio around 70-80%. 170-180 bpm would be in the 90-95% of maximum range for your age which is tough on your body- if you feel you are an elite athlete, then go for it, but if I push myself to that level I get physically ill. That is, for me, the main reason I monitor my heart rate: to avoid pushing myself too hard and seriously regretting it. If you aren’t confident in the measures on the machines, you could buy a chest strap and wrist monitor of your own for around $100.