The PlayerMoveEvent fires many times a second when the player moves. Even if they're moving their head, this is why the answer given by Blue Dev is making your message print many more times than expected.
Instead of creating a new task every time the player moves in water. You should use a runTaskTimer scheduler and only create it if there is not one already running for the player.
// Create a map to store the player's UUID and their task
public final Map<UUID, BukkitTask> playersBeingDamaged = new HashMap<>();
@EventHandler
public void OnWater(PlayerMoveEvent e) {
    Player p = e.getPlayer();
    // Create an optional which may contain the BukkitTask
    Optional<BukkitTask> bukkitTaskOptional = Optional.ofNullable(playersBeingDamaged.get(p.getUniqueId()));
    if (!(p.getLocation().getBlock().getType().equals(Material.WATER))) {
       // If the player is not in water and they have a task, cancel and remove it from the map
       bukkitTaskOptional.ifPresent(it -> {
           it.cancel();
           playersBeingDamaged.remove(p.getUniqueId());
        });
    } else {
       // If they're in water and have a task already, return; don't do anything more
       if(bukkitTaskOptional.isPresent())
           return;
       // Create the task for the player which will have a delay of 0 ticks and run every 20
       BukkitTask task = Bukkit.getScheduler().runTaskTimer(
               plugin,
               () -> p.sendMessage("Water Damage"),
               0L,
               20L
       );
       // Add the UUID and the task to the map
       playersBeingDamaged.put(p.getUniqueId(), task);
    }
}
If these tasks will be created often, a more efficient way would be to have a runTaskTimer running continually that iterates over a map of UUID's, get the player and their location, and then perform the action if they meet the conditions. They get removed from the map if they don't meet the conditions (e.g. in water). The PlayerMoveEvent is only used to add them to this map when they're in water.
Here's an example of that:
public class MyRunnable extends BukkitRunnable {
    @Override
    public void run() {
        for(UUID uuid : playersBeingDamaged){
            Player player = Bukkit.getPlayer(uuid);
            if(player == null || !player.getLocation().getBlock().getType().equals(Material.WATER)){
                // Player is offline OR they're not currently in water, remove them and continue
                playersBeingDamaged.remove(uuid);
                continue;
            }
            player.sendMessage("Water damage");
        }
    }
}
And this task can be started in your onEnable like so:
BukkitTask myTask = new MyRunnable().runTaskTimer(plugin, 0L, 20L);
P.S. playersBeingDamaged will need to be somewhere accessible to your runnable class and your listener.