This is really Rapace's thing, he was a French paratrooper. He will know a lot more, the second pic is jump wings, the beret and beret badge looks very much like the 1er RPIMa beret badge.
It's the same badge, but 1er RPIMa wasn't in Algeria AFAIK. It's definitely either a Marine or Colonial Para regiment, though.
(French Colonial units have been rocking the anchor since the 1700's.)
Since he (Kevinza's Gramps) was in Algeria; based on the insignia, he may have been in one of the Colonial Para regiments (2e, 3e, or 6e RPC). 1er REP, 1er RCP, and 9e RCP were there, but would not have had anchor on their badge.
The jump wings are standard french para wings; doesn't really tell us much other than that he was airborne. (Which we knew.)