Generally speaking it's a calories in vs. calories out game. The average adult male uses about 2400 cal/day so if you consume more than that you gain weight, less and you lose weight. Though there is some variation across individuals. Counting calories is relatively trivial, especially after a few days and you've memorized the values for the foods you commonly eat. I think it would be a worthwhile exercise to count your calories for a week or so to see if you actually are running at a deficit.

Now if you are in fact consuming too few calories to maintain your weight then you will burn your body fat and then eventually start burning muscle tissue when the body goes into starvation mode. This is quite a serious condition and unlikely to occur unless you are undergoing some extreme circumstances, which your post does not seem to indicate.

If you were doing power lifting, for example, then you might need to consider some protein shakes to help build muscle. But for just everyday living including average level work outs the amount of protein most people consume is more than enough.

What you should be doing is increase your intake of good quality fats and oils. They are more calorie dense than any carbohydrate but do not result in your insulin spiking which has a host of other issues. Animal fats are great so load up on butter and fatty meats. Nut and seeds oils are also fine BUT only as long as they are not heated. Sadly deep fried foods like french fries and potato chips are all cooked using nut and seed oils now so are not recommended. Margarine also is bad. And of course transfats AKA hydrogenated oils are to be avoided like the plague.

Carbohydrates are fine in moderation but empty calories like candy and soda are terrible for you for all sorts of reasons. The more complex the carbohydrate is the longer it takes to be converted to blood sugar and the lower the resulting insulin spike.

Unless you are a top tier athlete you don't generally use enough calories while exercising to make a huge impact. I forget the exact figure but running for an hour only uses something like 600 calories. Of course if you're already losing weight then increasing the amount of exercise you do will compound that. But it doesn't take a lot of additional food to offset calories burned in exercise.