Hello,
You will not be able to lower your carbs right away without becoming genuinely sick: lightheaded, loss of vision, memory impairment, blood pressure problems... The transition to a lower carb sugarless diet must be gradual.
Giving up grain foods is a good idea to start with. However, you shouldn't deal with carb cravings by switching to other types of carbs such as fruit. I think it's extremely helpful to use a food calculator such as the popular fitday to learn just how much protein, carbs, and fats you are eating.
Find the baseline protein that you want to eat, set a maximum of carbs you want to eat, calculate the baseline calories you need to eat each day, and then get the balance of calories from fat. My dietary ratio is: 20% protein (80g), 60% fat, and 16% carbohydrate.
During the beginning, you can address carb cravings (if you have them, which you probably will) by eating more protein. Once you are better adapted to lower/low carb, you can reduce the protein to your calculated baseline amount. (Somehow protein has a metabolic effect of addressing carb needs whereas fat, although a superior fuel, doesn't. I don't recall the details of this.)
A carb craving is commonly considered to be "hunger" but it is actually an affect of the mood, the mind, and brain. It's an insulin imbalance. Shakiness, fogginess, irritability are all carb cravings, not hunger. Real hunger is a sensation in the stomach that doesn't affect the mood or nervous system.
Paleo is simple and easy. This is one of the appeals of the diet. You will eventually find that you are eating much less food because the food is more concentrated in nourishment. Each one of our meals is about the portion size of a restaurant appetizer.
If you are used to eating fast food you find the flavors of simple foods to be bland. Use natural spices and willpower until you get accustomed to appreciate the variety of subtle flavors present in natural unprocessed food.
Good luck and good health
Puma
Follow Mothering