While your daily banana will give you 12% of your RDA of potassium, you'll likely want a bit more than that to avoid cramping. Have a can of salmon (18%) or a small handful of spinach (16%).
As to your symptoms of being "suddenly lightheaded, nauseous, and my appetite vanishes... in-between my meals." This could be your adjustment to low carb, as people have suggested. Alternatively,e it could be you not eating enough calories (very easy to do on paleo). Or perhaps, as an ex-vegetarian you're still nauseated by meat and tacitly worried that if you eat any meat and fat it won't be "sustainable" and "could have harsh effects on my gall bladder and blood levels." You must realise that there's no reason to infer from being 'lightheaded, nauseous and no appetite' to 'my gall bladder and blood levels may be damaged!'
From looking at your blog- where you say that you perk up when you eat, but feel rough until you can find something else to eat- I think the evidence is pretty good that you're just not eating enough. Plausibly you're eating a small, 'normal' serving of meat, say 40g protein and 300 calories, and then feeling hungry until the next meal when you eat a pitifully small portion of your overall calorie needs again. If you're interested in weight loss then it might seem the last thing you want to do to purposefully eat more food when you have no appetite, but it seems quite likely that that's what you need, given that you are clearly 'hungry' physiologically, regardless. If you are going to inadvertently calorie restrict, then you will feel like you're in a starvation experiment (i.e. awful).
Thus, I suggest cooking up a large amount of meat: enough for a whole day's worth of protein (100-150g of protein). And eat as much of it as you feel like. Furthermore, don't try to get all your calories from protein, which can seem like the only thing you are allowed to eat on the paleo diet. Once you've had 15-25% of your calories from protein, then the other 75-85% are going to have to come from carbohydrate or fat (including some from your own body fat, of course). I note on your blog that you say that you're eating lean protein, which might explain it. If you are just eating lean protein and vegetables, then it's basically impossible to eat anything. You will have to either eat fruit and nuts (a bad idea imo, since they're high in fructose and PUFA), sweet potatos or some other kind of starch (not my preferred choice, but works for many, especially if you're very active and not looking to lose weight) or lots of added 'animal' fats (within which category I include coconut).