Should be dead easy you are just getting your flesh protein from fish instead of beef. If you eat yogurt I assume you might be open to butter or ghee, if not as others have said there is olive oil and coconut oil to cook with. If you can get the grass, fed hormone fed beef you are good but IMHO wild fish is probably a lot better than supermarket beef. So you should have no problems eating fish as your main primal protein.
Eating primal is not a diet, it is a way of life.
PS
Don't forget to play!
i think we can easily live on seafood. alot of our earlier ancestors did. in fact i have thought a fair bit about doing a few months pescetarian to see how i go. where i live i can gather lots of shellfish so that helps. loadsa recipes out there for fish, clams, mussels, abalone etc that are already by default primal or paleo. nicoise salad is tuna, eggs and salad for example. smoked salmon goes awesomely with eggs and avocados. what i would do is make some kind of omlette for breakfast. or just some panfried fatty fish. fish roe omlette. prawn and avocado omlette. a bowl of 24 hr yoghurt with seeds or nuts. etc. nicoise salad, cockle soup of for lunch. some form of sea food dish for dinner. smoked fish pie with cauliflower instead of potato top, creamed abalone with coconut cream and steamed veges, fish curry, cockle curry etc.