Try allowing multiselection, drag and drop plus a contextual menu for repositioning 1 or more items.
Allow Shift
+ select for multiple items (or single click for one item). Then, the Right click or Contextual menu can serve up bulk actions (if multiple are selected). They can still reposition selected items by traditional drag and drop, in addition to an explicit popup menu.
NOTE: 'Move' may not be the right term for your app, since they're not changing the location, but repositioning; perhaps you can test with users to see what best conveys the concept.

download bmml source – Wireframes created with Balsamiq Mockups
Google drive allows similar actions: here's a pic of their grid view, with multiselect:

This model allows:
- 1 click for single selection
- Shift click for multiple
- Contextual actions for the selected items
As for pagination, I don't see what the advantage is in your application. Is it simply an implementation detail, because returning large amounts of results is an expensive API call?
If so, maybe have a 'Load more' button.