Lost all my bookmarks one by one on all my periphery equipment (iPhone5, ipads, kids' iPhone, etc...) then, finally, my MacBook Pro.
Lost more of my hair due to hair pulling of self...
So, here's how I got them back:
1. The issue is with syncing Safari with the iCloud
2. Open iTunes on your computer
3. Plug device into computer for sync
4. DESELECT Safari under iCloud on device
5. On iTunes, go to Info tab
6. Scroll down to Other
7. Select Sync Safari Bookmarks ( This option is not available if Safari is ON on your device. This will work wether or not the bookmarks are on your computer or not... Mine magically came back from the ether)
8. Select Apply and begin sync
9. Rejoyce and buy a frosty beverage in the name of an "internet solution".
((your results may vary, but it's worked on 5 of my devices including my MacBook))
Good luck!