A área de trabalho pública é parte do que está acontecendo. Os ícones que você vê na área de trabalho são uma combinação da pasta Desktop do seu perfil, da pasta Desktop do perfil Público / Todos os usuários e dos ícones especiais Meu computador / Lixeira / Rede / etc escolhidos para o seu perfil.
O papel de parede é outra história. Os papéis de parede são definitivamente armazenados separadamente por perfil de usuário no Windows e não serão alterados para um usuário apenas porque outro alterou um arquivo em seu próprio perfil. A Política Local pode desempenhar um papel nisso. Você pode usar a política de grupo em uma máquina local para definir um papel de parede para todos os usuários. Mas eu não acho que foi o que aconteceu aqui.
Acredito que você configurou todos os seus usuários com a mesma conta da Microsoft. A partir do Windows 8, o Windows também desejará associar uma conta da Microsoft a cada usuário. Contas da Microsoft podem sincronizar algumas configurações através da nuvem ... incluindo Desktop Wallpaper. Se todos os seus usuários estiverem conectados à mesma conta da Microsoft, alterar uma configuração de perfil sincronizado em um usuário também o alterará para os outros.
Se você deseja desvincular esses perfis da conta da Microsoft, não é difícil encontrar instruções por meio do Google. Só tome cuidado ... Já ouvi histórias em que desvincular a conta pode resultar na perda de acesso a seus perfis na máquina. Você ainda poderá usar a máquina, mas terá que recomeçar com um novo perfil.