We investigate the influence of a Bose-Einstein condensate (BEC) on the properties of immersed impurity atoms, which are trapped in an optical lattice. Assuming a weak coupling of the impurity atoms to the BEC, we derive a quantum master equation for the lattice system. In the special case of fixed impurities with two internal states the atoms represent a quantum register and the quantum master equation reproduces the exact evolution of the qubits. We characterise the qubit dephasing which is caused by the interspecies coupling and show that the effect of sub- and superdecoherence is observable for realistic experimental parameters. Furthermore, the BEC phonons mediate an attractive interaction between the impurities, which has an important impact on their spatial distribution. If the lattice atoms are allowed to move, there occurs a sharp transition with the impurities aggregating in a macroscopic cluster at experimentally achievable temperatures. We also investigate the impact of the BEC on the transport properties of the impurity atoms and show that a crossover from coherent to diffusive behaviour occurs with increasing interaction strength.