That is exactly the point. Holding elections, even peaceful, transparent elections, is not the same thing as "replacing the government." Most government employees and non-employees who heavily influence policy are not elected and can't be replaced through elections.
This reduces into a linguistic question of what Karl Popper actually meant, which is kind of .. unfalsifiable.
At least in UK politics, 'government' explicitly means "Her Majesty's Government", ie the Prime Minister and those they appoint to assist them. Not the Crown, not the permanent state.
Sure they can be replaced peacefully, in theory. Governments do occasionally fire civil servants for loyalty reasons, though it's controversial, since those positions aren't supposed to wield political power. Think of Bush's prosecutor purges.
Though I agree that Popper doesn't focus enough on degrees of change or feasibility of change (if the only parties essentially agree on everything, is government really replaced?)