hmmm...is this an iPad?
I don't have an iCloud icon on my safari app in my iPhone 5. However, wherever I do see this, it typically means the items there are not located on that device, but in iCloud, or on some other device. I'm really not sure how to manage these...maybe someone else can chime in?
It will eventually clear out.It's still recognizing the device before it was restored as well as after you restored.
Seems like I just have to be patient.