Maybe you can tell me where in the Perl documentation you found the sed command?

As a next step, I would recommend that you add comments indicating where you wrote the code that you think implements the steps I outlined for you to undertake.

Also, it often helps us to help you better if you also tell us what the error message is, possibly together with the input data.

{
    local undef $/;
    while (<MYINPUTFILE>) {
        ...
    }
}
[download]

while (readline into $line)
  if $line starts with 'priority'
    print $line if 'priority not already seen'
    remember that priority was seen
  end
  else if $line is blank
    forget that priority was  seen
  end
  else
    print $line
  end
end
[download]

while (readline into $line)
  if $line starts with 'priority'
    replace 'priority' with 'bandwidth' if 'priority already seen'
    remember that priority was seen
  end
  else if $line is blank
    forget that priority was  seen
  end
  print $line
end
[download]

It's basically what Corion already said, but it has the basic structure of what your code might look like. Now all you have to do is translate it.

Update: Changed pseudocode to do substitution rather than skip printing.